Дискретная математика. Раздел : теория графов : выпуск 2
Покупка
Тематика:
Дискретная математика
Издательство:
Издательский Дом НИТУ «МИСиС»
Год издания: 2000
Кол-во страниц: 37
Дополнительно
В пособии приведено описание лабораторной работы, в которой на основании информации о графе, заданном одним из матричных способов, осуществляется построение его локальных характеристик.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.04: Прикладная математика
- 03.03.01: Прикладные математика и физика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
№452
МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ «МСДВРАПИИ
м о с к о в с к и й ГОСУДАРСТВЕННЫЙ ИНСТИТУТ СТАЛИ и СПЛАВОВ
{ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра автоматизированных систем управления
Рытнкова Ю.В., Булхов Н.Н., Прокопчук Ю.Ю.
Одобрено методическим
советом института
Дискретная MaTeMaivKa
Раздел: Теория графов (выпуск 2)
(Переиздание)
Лабораторный практикум
для студентов специальности 0719 и 2202
НТБ
МИСИС
СЧЗ
ГЛ.КОРПУС
Москва 2000 г.
Аннотация в пособии приведено описание лабораторной работы, в 1а}торой на основании информации о графе, заданном одним из матричных способов, осуществляется построение его локальных характеристик. © Московский государственный институт стали и сплавов (МИСиС) 2000
Рьпнкова Ю В., Будхов Н.Н.. Прокоптук Ю Ю.
ЛАБОРАТОРНАЯ РАБОТА 2
Преобразование матриц, характеризующих
графы. Выявление информации о графе,
заданном одним из матричных способов
(4 часа)
1. Цель работы
Ознакомиться с ма1ричными способами задания графа и
на этой основе научиться выявлять о нем определенную информацию.
2. Теоретическое введение
2.1. Для любых двух элементов L к V совокупности графов А можно поставить вопрос о степени их сходства в том или
ином смысле. Формула «граф L похож на граф Z,'* выражает
хотя и осмысленное, но все же пока не формальное отношение
на А, которое допускает различные уточнения. Два из них: равенство и изоморфность графов мы и рассмотрим здесь.
2.2. Не вызывает затруднений формулирование точного
определения наибольшей степени сходства графов - их тождественности, или равенства, обозначаемой знаком =, поскольку графы представляют собой тройки, а равенство последних эквивалентно по определению совпадению их соответствующих компонент. Поэтому говорят, что граф L = {X,U,P)
находится в шь
ношении равенства с графом L =\Х ,U ,Pj,
или, короче, jac
вен ему, и обозначают этот факт так: L~L\
если:
1) Х = Х;
2)f/ = (/';
3) (Vx.^eX,
и^щ\р{х,и,у)<;>р\х,и,у\.
Несложно убедиться, что отношение равенства, или просто
равенство графов есть антисимметричная эквивалентность на их
множестве.
Пример 1. Графы Z-i^ и Zjg, диаграммы которых приведены на рисунках 1а) и 16) соответственно, равны.
IV HI /
4 \ IV IVI
£
У1
d
U
а)
б)
в)
Рис 1.
2.3. Очевидно, что графы Z-jg и Lj^, изображенные на
рис. 1в) и 1г) соответственно, не равны, а также каждый из них
не совпадает ни с одним из предыдущих. Так, графы L^^ и Lj^
различны, поскольку не выполняются условия 1) и 2). С другой
стороны, несомненно и их сходство, состоящее в том, что существуют переобозначения вершин и ребер графа Lj^ метками из
множеств Xi^-\a,fi,y,S]
вершин и Ui^ = {a,b,c,d}
ребер
графа Lj^ соответственно, которые «превращают» его в граф Z.^^ .
Таким переобозначением для вершин может быть, в частности,
следующее:
Таблица 1
^к
^\г
I
а
II
Р
III
У
IV
д