Лекция: Графы. Виды и алгоритмы обработки

Основные понятия и виды графов

• Вершина (vertex, node)
• Ребро (edge, link)
• Смежные вершины
• (adjacent vertices)
• Путь (path) – последовательность
• вершин, в которой следующая
• вершина (после первой) является
• смежной с предыдущей –
• все вершины и ребра различны
• Путь: (10, 8, 3, 5)

Основные понятия и виды графов

• Цикл (cycle) – путь, в котором
• первая и последняя вершины
• совпадают: (4, 6, 7, 8, 3, 4)
• Степень вершины
• (vertex degree) –
• количество ребер,
• инцидентных вершине
• deg(7) = 2, deg(1) = 3

• ТЕОРЕМА

• В ГРАФЕ G(V, E) СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ЧИСЛУ РЕБЕР ГРАФА:

• ВЕРШИНА НАЗЫВАЕТСЯ ЧЕТНОЙ (НЕЧЕТНОЙ), ЕСЛИ ЕЕ СТЕПЕНЬ – ЧЕТНОЕ(НЕЧЕТНОЕ) ЧИСЛО.

• ТЕОРЕМА

• ЧИСЛО НЕЧЕТНЫХ ВЕРШИН ЛЮБОГО ГРАФА – ЧЕТНО.

• СЛЕДСТВИЕ

• НЕВОЗМОЖНО НАЧЕРТИТЬ ГРАФ С НЕЧЕТНЫМ ЧИСЛОМ НЕЧЕТНЫХ ВЕРШИН.

Основные понятия и виды графов

• Полный граф (complete graph) – это граф, в котором каждая пара различных вершин смежные (каждая вершина соединена со всеми)
• Дополнением графа называется граф с теми же вершинами и имеющий те и только те ребра, которые необходимо добавить к исходному графу, чтобы он стал полным.

• ДОПОЛНЕНИЕ ГРАФА

• A

• B

• C

• D

• A

• B

• C

• D

• A

• B

• C

• D

• Количество ребер в полном
• неориентированном графе:

Основные понятия и виды графов

• Насыщенность D графа (density):
• Насыщенный граф (dense graph) – это граф, в котором количество ребер близко к максимально возможному (D>0.5)
• Разреженный граф (sparse graph) – граф, в котором количество ребер близко к количеству вершин в графе (D<0.5)