Способы представления графов.

Задать граф значит описать множество его вершин и ребер, а также отношения инцидентности.

Отношением инцидентности, определяющей матрицей E _ij, имеющей m строк и n столбцов.

Если ребро ei инцидентно вершине V_j, то в матрице элемент E _ij =1, иначе элемент равен 0.

 

ei \ Vj	I	II	III	IV	V	VI

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

если ребро e_i инцидентно V_j, при этом V_j является началом ребра, то E_ij =-1, если V_j является концом ребра, то E_ij =1, иначе E_ij =0.

Если ребро является петлей, то в матрице инцидентности элемент E_ij =а, где а >1

 

ei \ Vj	I	II	III	IV	V
	-1
		-1
		-1
		-1

 

В памяти ЭВМ матрицы инцидентности задается двумерным массивом.

Способ представления матрицы инцидентности не является экономным, так в строке значатся только 2, а остальные нули.

Поэтому существует другие методы

Список ребер

Список ребер имеет структуру списка, каждая строка содержит номера вершин, инцидентных ребру:

 

ei \ Vj
	I	II
	I	III
	II	IV
	I	V
	II	V

 

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

Представление более компактно.

Матрицы смежности.

Матрица размера n×n, строки и столбцы нумерованы в соответствии с номерами вершин на пересечении строки и столбца ставится 1, если вершины смежные и 0, если они не смежные.

 

ei \ ej	I		III	IV	V	VI
I
II
III
IV
V
VI

 

ei \ ej	I	II	III	IV	V
I
II
III
IV
V

 

Для ориентированных графов матрица смежности будет иметь треугольный вид, так как инцидентные вершины будет определяться с учетом направления.

В памяти ЭВМ матрица смежности представляется двумерным массивом, содержащим 0 и 1, если V_i смежно с V_j, иначе – 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p(1)=3

p(2)=2.

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

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

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

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

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

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

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

Частью 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₂)

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

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

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

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

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

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

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

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

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

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

Связные компоненты графа.

Две вершины Vi и Vj называются связными в графе G, если в нем существует маршрут для которого Vi и Vj являются началом и концом.

Граф G назывется связным, если каждая пара его вершин явл. связной, иначе граф называется не связным.

Если вершина V графа G связана с какой-либо другой вершиной, то она связана сама с собой.

Отношение связности 2-х вершин, заданное на множестве обладает свойствами рефлексивности, симметричности и транзитивности. Проверить или показать, каким образом отношение связности является отношением эквивалентности. Следовательно определяет разбиение мн. вершин графа на непересекающиеся подмножества.

Вершины одного и того же множества связаны между собой, а вершины различных мн. – не связаны, поэтому в графе G нет ребра, которое бы имело концы в вершинах из разных множеств.

Расстояния в графе.

Пусть G – неориентированный граф, v¢ и v² - любые две его вершины. Тогда существует связывающая их простая цепь М (е₁,е₂,…, е_q). Если количество q ребер этой цепи – не минимальное из возможных, то существует цепь М¢ (е¢₁,е¢₂,…, е¢_q¢), связывающая v¢ и v² и имеющая меньшее число ребер. Если М¢ не минимально, то можно найти связывающую v¢ и v² цепь с еще меньшим количеством ребер и тд. Однако этот процесс уменьшения числа ребер можно повторить не более q раз, так как это число каждый раз уменьшается не меньше ем на единицу. Поэтому существует связывающая v¢ и v² цепь М^~(е^~₁,е^~₂,…, е^~_p) с минимальным количеством ребер р. Минимальная длина простой цепи с началом v¢ и концом v² называется расстоянием d(v¢,v²) между этими вершинами.

Считая каждую вершину v неориентированного графа связной с самой собой, мы по существу ввели нулевые маршруты, не содержащие ребер, с началом и концом в любой вершине vÎG. В соответствии с этим расстояние d (v,v) между вершиной v и ею самою равно 0. Для любой пары v¢,v²ÎG различных вершин d(v¢,v²)>0, т.к. связывающая эти вершины цепь состоит хотя бы из одного ребра.

Расстояние d(v¢,v²) удовлетворяет аксиомам метрики:

1) d(v¢,v²)³0, причем d(v¢,v²)=0, когда v¢=v²;

2) d(v²,v¢)= d(v¢,v²);

3) справедливо неравенство треугольника: d(v¢,v²)+d(v²,v²¢)³d(v¢,v¢²).

В особом доказательстве нуждается только последнее свойство. Пусть M¢ (v¢,v²) и М² (v²,v¢²) – минимальные простые цепи, связывающие v¢ с v² и v² с v¢². Тогда последовательность ребер М, в которой сначала идут все ребра цепи M¢, а затем ребра цепи M², - это маршрут, связывающий v¢ и v¢² и имеющий длину d(v¢,v²)+d(v²,v²¢). Как показано ранее, если этот маршрут не является простой цепью, то можно найти более короткую цепь М^~, связывающую v¢ и v¢². Поэтому во всяком случае минимальная связывающая эти вершины цепь имеет длину, не превосходящую d(v¢,v²)+d(v²,v²¢).