1 Основные понятия теории графов Леонард Эйлер, 1736 г. Кирхгоф – электрические цепи Кэли – органические изомеры Гамильтон – головоломки Д.Кениг, 1936. - презентация

1 1 Основные понятия теории графов Леонард Эйлер, 1736 г. Кирхгоф – электрические цепи Кэли – органические изомеры Гамильтон – головоломки Д.Кениг, 1936 Теория ориентированных и неориентированных графов

2 2 Неориентированные графы Вершины x и y смежныхе Х – множество вершин, U – множество ребер Ребра g и h смежныхе Вершина x и ребро g инцидентны - существует ребро, соединяющее эти вершины - существует вершина, являющаяся общим концом этих ребер - вершина x является концом ребра g

3 3 Неориентированные графы Утверждение 2 Количество вершин нечетной степени четно Вершина x изолированная, если она не имеет смежныхх вершин - степень вершины x ( количество ребер, инцидентных вершине x ) Утверждение 1

4 4 Неориентированные графы Граф есть пустой граф, если Обозначение: Граф есть полный граф, если все его вершины смежных Обозначение: Граф есть двудольный граф, если причем вершины каждой доли несмежныхх. Полный двудольный

5 5 Матрицы неориентированных графов Матрица смежности Матрица инцидентности

6 6 Матрица достижимости Матрица Oперации сложения и умножения xyx+yxy Матрица достижимости

7 7 Изоморфизм и планарность графов Графы и называются изоморфными, если существует биекция сохраняющая отношение смежности. Обозначение: Изоморфные графы

8 8 матрицы инцидентности и могут быть получены друг из друга перестановками строк и столбцов. Изоморфизм и планарность графов матрица смежности может быть получена из матрицы смежности одинаковыми перестановками строк и столбцов., причем : Теорема 1 Теорема 2

9 9 Изоморфизм и планарность графов Граф называется картой (плоским графом), если он изображен на плоскости без самопересечений ребер. Планарные графы Граф называется планарным, если существует изоморфная ему карта.

10 10 Изоморфизм и планарность графов планарен тогда и только тогда, когда в нем нет подграфа, который можно сжать до или Теорема (Понтрягина-Куратовского). Граф

11 11 Изоморфизм и планарность графов Пример непланарного графа

12 12 Граф называется связным, если Компоненты связности графа Компонента связности графа есть максимальный связный подграф этого графа - разбиение графа порожденное отношением достижимости на графе - число компонент связности