Дискретная математика. Раздел : теория графов : выпуск 2

№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 
д