63. Идентификация графов, заданных своими представлениями.

Граф может быть представлен разными способами, иногда нелегко определить, одинаковые ли графы заданы разными представлениями.

Вид матрицы смежности и списка ребер зависит от способа нумерации вершин или ребер графов.

Граф считается полностью заданным, если его нумерация зафиксирована.

Графы отличаются друг от друга только нумерацией вершин называются изоморфными.

Перенумерация вершин графов задается строкой ₁, ₂, …, _n, состоящих из новых номеров вершин, расположенных в исходном порядке.

Новая матрица получается из исходной матрицы смежности, перемещением элемента E_ij в _i строку и _j столбец. То есть в результирующей перестановке k строк и n столбцов исходной матрицы.

Поэтому, для того, чтобы узнать представляют ли 2 матрицы изоморфные графы необходимо в 1 из матриц выполнить все возможные перестановки строк и столбцов.

Если в результате на каком-либо шаге будет получена матрица тождественно совпадающая с проверяемой, то графы заданные этими матрицами являются изоморфными.

Для выполнения этой проверки необходимо провести n! перестановок.

64. Обходы графов.

Обход графов – это некоторое систематизированное перечисление его вершин (и/или ребер).

Наибольший интерес представляют обходы, использующие локальную информацию о графе (матрицу смежности, инцидентности).

Среди всех обходов наиболее известны: обходы в ширину и в глубину

Для реализации обходов в глубину используется структура стэк; в ширину – очередь.

65. Степени вершин графа.

Если же неориентированный граф, то количество ребер, инцидентных вершине называется локальной степенью или степенью вершины например степень вершини обозначается p(v)

p(1)=3

p(2)=2.

Если в графе степени вершины конечны, то граф назвается локально конечным.

Если для графа заданого матрицей инцидентности или матрицей смежности,то степень вершин можно определить след образом:

p(Vj)=вверху m,внизу i=1 E_ij.

Висячая вершина – вершина степени 1.

Висячее ребро – ребро соответствующее висячей вершине.

Изолированная вершина имеет степень 0.

66. Операции с частями графа.

Частью HG (часть Н графа G) называется граф Н, если множество его вершин содержится в множестве вершин графа G, а множество ребер графа Н является подмножеством множества вершин графа G. Если множество вершин графа А и В совпадают то такой подграф называют суграфом.

Подграфом G(U) графа G с множеством вершин U, являющихся подмножество множества вершин V, называется часть, которой принадлежат все ребра графа V с обоими концами из множества U

Дополнение Н части Н будем определять множество всех ребер графа G не принадлежащих Н.

Сумма:

V(H₁H₂)=V(H₁) V(H₂)

E(H₁H₂)=E(H₁) E(H₂)

Разность:

V(H₁H₂)=V(H₁) V(H₂)

E(H₁H₂)=E(H₁) E(H₂)

Две части графа Н₁ и Н₂ не пересекаются по вершинам, еслит они не имеют общих вершин.

Сумма частей Н₁ и Н₂ не пересекающихся по вершинам называется прямой суммой.

67. Маршруты, цепи, циклы.

Маршрутом в графе G называется конечная или бесконечная последовательность ребер e₁,e₂,…,e_n, что каждые 2 соседние ребра имеют общую инцидентную вершину.

Одно и то же ребро может встречаться в маршруте несколько раз.

Маршрут называется открытым, незамкнутым, если его концевые вершины различны, иначе он называется замкнутым.

Число ребер в маршруте называется длиной маршрута.

Если начальная и конечная вершины совпадают то он называется цикличным.

Маршрут называется цепью, если каждое ребро встречается не более 1-го раза и простой цепью, если любая вершина инцидентна не более чем 2-м ребрам.

Цикличный маршрут называется циклом, если он является цепью и простым циклом, если он является простой цепью.