какая-то теория / способы задания графов
.pdf
3. Список ребер
3.Список ребер
•Списком ребер можно задать граф без кратных ребер.
•Ребро представляется парой вершин, инцидентных ему, например е =(v, w).
•Для н-графа порядок вершин в строке произволен, для ор-графа первым стоит номер вершины–начала ребра.
4.Рисунок
•Рисунок или геометрическая интерпретация появляется, если сопоставить вершинам точки плоскости, ребрам – линии на плоскости, причем, линия соединяет только те точки, которые соответствуют вершинам, инцидентным данной линии-ребру.
•Граф для которого возможна геометрическая интерпретация на плоскости, называется планарным.
Пример: список ребер н-графа
E={(a,a), (a,b), (a,c), (b,c)}
Пример: список ребер ор-графа
E={(a,a), (a,b), (a,c), (с,a), (b,c)}
ТЕОРИЯ ГРАФОВ
Изоморфизм графов
Изоморфизм графов
Один и тот же граф может иметь несколько графических изображений, которые можно получить, изменяя расположение вершин и придавая ребрам разную геометрическую форму и длину
С другой стороны, два одинаковых, на первый взгляд, изображения могут задавать разные графы. Так, графы ниже геометрически одинаковы, но они отличаются нумерацией вершин.
В таких ситуациях необходимо четко определить понятие изоморфизма графов.
Изоморфизм графов
Изоморфизм графов
Замечание 1. Графы, содержащие различное число вершин или ребер, не являются
изоморфными.
Замечание 2. Графы, отличающиеся только
нумерацией вершин, являются изоморфными.
Замечание 3. Изоморфизм неориентированных графов есть отношение эквивалентности, так
как обладает свойствами рефлексивности,
симметричности и транзитивности.
При замене графа любым ему изоморфным все
свойства графа сохраняются.
Изоморфизм графов
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности можно
получить одну из другой одинаковыми
перестановками строк и столбцов.
Чтобы проверить по матрице смежности изоморфность графов с числом вершин n ,
потребуется в общем случае n! перестановок.