Способы задания графов

Мы познакомились с двумя способами описания графов: графическим, и в виде двух множеств вершин V и ребер Е, когда каждое ребро е Е определено парой инцидентных ему концевых вершин (v', v ").

Рассмотрим другие способы, используемые в теории графов.

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

Пусть v_1,v₂,...,v.,...,v_n - вершины графа G; e₁, e₂,...,e.,... ,e_m- ребра. Отношение инцидентности задается:

• матрицей инцидентности || _ij || размера т х п: по вертикали и горизонтали указываются вершины и ребра соответственно, а на пересечении i -и вершины и j -го ребра проставляется 1, если они инцидентны, и 0 - в противном случае, т.е.

n списком ребер графа, представленным двумя столбцами: в левом перечисляются все ребра, а в правом – инцидентные ему вершины.

n матрицей смежности -- квадратной матрицей размера п х п по вертикали и горизонтали перечисляются все вершины графа, а на пересечении k-и и l -й вершин 1 – если вершины смежны и 0 – в противном случае.

Определение. Назовем цепью последовательность ребер такую, что каждое ребро и_k соприкасается одним из концов с ребром u_k-1 (если оно существует), а другим — с u_k+1 (если оно существует).

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

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

Определение. Две вершины называют связными, если существует какой-либо путь между ними.

Определение. Назовем цепь простой, если никакое ребро не входит в нее дважды. Цепь, не являющейся простой называют составной.

Определение. Назовем цепь элементарной, если никакая вершина не входит в нее дважды. Цепь, не являющейся элементарной, называют неэлементарной.

Определение. Циклом называется конечная цепь, в которой начало первого ребра совпадает с концом последнего.

Определение. Назовем цикл элементарным, если все вершины, через которые он проходит, различны (естественно, за исключением начальной и конечной, которые совпадают по смыслу понятия цикла).

Определение. Назовем цикл простым, если все ребра, через которые он проходит различны.

Циклы называются эквивалентными, если они проходят одни и те же вершины в одинаковом порядке.

Определение. Граф G называется связным, если любые две вершины в нем связны.

Пусть - множество вершин, соединенных цепью с .

Определение. Компонентой связности называется подграф графа G, ассоциированный с подмножеством .

Определение. Дерево – это связный граф, который не имеет циклов.

Ребра называются циклическими, если они принадлежат хотя бы одному циклу.

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

Св-ва графов.

1. Сумма степеней всех вершин графа равна удвоен. числу его ребер.

След-е. У полного гр. – р=в*(в-1)/2.

2. Число нечетных вершин любого г. четно.(нечет. вершина=с нечетн. степенью).

След-е. Если в г. есть 1 нечет. вершина, то д. б. по кр. мере еще одна.

3. В любом г., в кот. более 1 вер-ны, всегда есть 2 вер-ны с одинак. степенями.

4. Если у г. число вершин n>2 и в нем только 2 вер-ны с одинак. степенями, то в г. есть либо изолир. вер-на, либо 1 со степ. n-1.

5. Если все простые циклы четной длины, то нет циклов нечетных.

6. Любой подграф г. однозначно опр-ся набором его вершин.

7. Дерево, имеющее n вершин, им. ровно n-1 ребро.

Сл-е. Дерево сод. только антиц. ребра и обязат. им. висячие вершины(степень кот.=1).

8. Удаление из связного г. циклич. ребра не меняет связности, удаление же антициклич. делает г. несвязным.

Мост – ребро, удаление кот. нарушает связность г.

9. Любые 2 в-ны дерева им. только 1 элем. путь их соед-щий.

10. Если в связном г. n вершин и n-1 ребро, то это дерево.

11. Из любого связ. г. можно получить дерево путем послед. удаления циклич. ребер(для связного надо удалить m-n+1).

Определение. Эйлеровым циклом называется простой цикл, содержащий все ребра.

Определение. Граф G = (X, U) называется эйлеровым., если он содержит эйлеров цикл.

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

Теорема. Связный граф G --= (X, U) является эйлеровым тогда и только тогда, когда каждая вершина G имеет четную степень. При этом начало цикла может находиться в любой вершине графа.

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

Определение. Конечный граф называется гамилътоновым, если он обладает либо гамильтоновым циклом, либо гамильтоновой цепью.

Дата добавления: 2015-07-11