Основные понятия теории графов: различия между версиями
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 9: | Строка 9: | ||
Граф - это набор вершин (точек) и соединяющих их отрезков (рёбер). | Граф - это набор вершин (точек) и соединяющих их отрезков (рёбер). | ||
− | + | Примеры: | |
Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ - количество вершин, а $M$ - ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10). | Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ - количество вершин, а $M$ - ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10). | ||
Строка 18: | Строка 18: | ||
Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный. | Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный. | ||
+ | |||
+ | ===Деревья=== | ||
+ | |||
+ | Дерево - это связный неориентированный граф без циклов. | ||
+ | |||
+ | Пример дерева | ||
+ | |||
+ | https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Tree_graph.svg/162px-Tree_graph.svg.png | ||
+ | |||
+ | Свойства дерева: | ||
+ | |||
+ | 1) У дерева с хотя бы 2 вершинами всегда есть висячая вершина - вершина степени 1. | ||
+ | |||
+ | Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины - ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) - ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1. | ||
+ | |||
+ | 2) У дерева с хотя бы 2 вершинами всегда есть две висячие вершины. | ||
+ | |||
+ | Действительно, если предыдущий алгоритм начать из висячей вершины, то мы уткнемся в другую висячую вершину. | ||
+ | |||
+ | 3) У дерева с $N$ вершинами всегда ровно $N-1$ ребро. | ||
+ | |||
+ | Давайте отрезать от дерева его висячие вершины - при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока $N > 1$. В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше. | ||
+ | |||
+ | 4) Между любыми двумя вершинами в дереве есть ровно один простой путь. | ||
+ | |||
+ | Действительно, если их два, то в графе есть цикл. Быть ноль их не может - ведь граф связный. | ||
+ | |||
+ | 5) Дерево - это минимальный по числу рёбер связный граф на $N$ вершинах. | ||
+ | |||
+ | Действительно, если есть связный граф, в котором меньше, чем $N-1$ ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве $N-1$ ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то. | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 16:20, 26 сентября 2019
Основные определения
Формальное определение:
Графом $G$ называется пара множеств $G = (V, E$, где $V(G)$ — непустое конечное множество элементов, называемых вершинами графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых ребрами графа. $E = \{(u , v)\ | u, v \in V\}$ — множество ребер графа $G$, состоящее из пар вершин $(u, v)$. Ребро $(u, v)$ соединяет вершины $u$ и $v$.
Простое определение:
Граф - это набор вершин (точек) и соединяющих их отрезков (рёбер).
Примеры:
Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ - количество вершин, а $M$ - ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).
Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.
Простой граф не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.
Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.
Деревья
Дерево - это связный неориентированный граф без циклов.
Пример дерева
https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Tree_graph.svg/162px-Tree_graph.svg.png
Свойства дерева:
1) У дерева с хотя бы 2 вершинами всегда есть висячая вершина - вершина степени 1.
Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины - ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) - ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1.
2) У дерева с хотя бы 2 вершинами всегда есть две висячие вершины.
Действительно, если предыдущий алгоритм начать из висячей вершины, то мы уткнемся в другую висячую вершину.
3) У дерева с $N$ вершинами всегда ровно $N-1$ ребро.
Давайте отрезать от дерева его висячие вершины - при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока $N > 1$. В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.
4) Между любыми двумя вершинами в дереве есть ровно один простой путь.
Действительно, если их два, то в графе есть цикл. Быть ноль их не может - ведь граф связный.
5) Дерево - это минимальный по числу рёбер связный граф на $N$ вершинах.
Действительно, если есть связный граф, в котором меньше, чем $N-1$ ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве $N-1$ ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin