Последние полгода Ёжик совсем не уделял внимание вопросам теории графов, хотя это, несомненно, одна из самых востребованных и прикладных областей математики на сегодняшний день

Последние полгода Ёжик совсем не уделял внимание вопросам теории графов, хотя это, несомненно, одна из самых востребованных и прикладных областей математики на сегодняшний день. Несколько примеров — моделирование географических карт (картографические сервисы современных поисковиков стали возможны благодаря достижениям теории графов), структур нейросетей, путей в видеоиграх — и этим список далеко не ограничивается.

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

Начнём же, не откладывая в долгий ящик!

Слова, входящие в терминологию теории графов, для удобства выделены квадратными скобками [вот так].

[Граф] — это математический объект, изображаемый в виде набора точек, некоторые (или все) из которых соединены друг с другом линиями. Эти точки называются [вершинами], а линии — [рёбрами]. В некоторых работах вершины могут называться [узлами], а рёбра — [дугами].

Графы принято обозначать как и множества — прописными латинскими буквами. Чаще всего используются буквы G и H, иногда — с нижними индексами. Множество вершин графа чаще всего обозначают буквой V, а множество его рёбер — буквой E. Итого, граф может быть обозначен, к примеру, следующим образом: G = (V,E), дословно: «Граф G — это упорядоченная пара множеств V и E».

Вершины принято обозначать строчными латинскими буквами.

Количество вершин графа называется его [порядком].

Итак, каждая вершина графа соединяется с некоторыми другими его вершинами при помощи рёбер. Говорится, что каждое ребро [связывает] две вершины, а сами вершины называются [связанными] друг с другом. О ребре, связывающем две вершины, говорится, что оно [исходит из] каждой из этих вершин, а сами вершины называются [концами] этого ребра (по аналогии с концами геометрического отрезка).

Рёбра, исходящие из одной и той же вершины, называются [смежными] или [соседними]. Смежные вершины называются [инцидентными] ребру, связывающему их.

У каждой вершины графа есть [степень] — это количество вершин, с которыми она связана. Понятно, что степень вершины графа не может быть больше его порядка, но не может быть и равна ему. Дело в том, что сама вершина не считается связанной с самой собой, поэтому наибольшая степень любой вершины графа на единицу меньше его порядка. Степень вершины v обозначается как deg(v) от английского слова degree («степень»).

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

Можно составить новый граф из части вершин и рёбер другого графа, взяв их так, чтобы каждое ребро, как и прежде, соединяло две вершины, и сохранив взаимосвязи рёбер и вершин. Составленный граф называется [подграфом] исходного графа.

Если каждая пара вершин графа связана, такой граф называют [n-полным графом], где n обозначает степень графа. Такой граф принято обозначать буквой K с индексом n, то есть K?.

Если, двигаясь по рёбрам графа, из каждой его вершины можно добраться до любой другой его вершины, то граф называется [связным], иначе — [несвязным]. Вообще, если от одной вершины графа можно, двигаясь по рёбрам, добраться до другой, говорится, что между этими двумя вершинами существует [маршрут] — последовательность рёбер, по которым необходимо пройти. Промежуточные вершины, через которые проходит маршрут, называются его [внутренними] вершинами, а вершины, которыми маршрут начинается и оканчивается, называются его [концевыми] вершинами или [концами]. Количество вершин, входящих в маршрут, называется [длиной] этого маршрута.

Маршрут определяется как упорядоченная последовательность вершин и рёбер, начинающаяся и оканчивающаяся вершинами, и в которой между каждой парой вершин расположено связывающее их ребро.

Частными случаями маршрута являются [путь] и [цикл]. Путь — это маршрут, вершины в котором не повторяются, и потому путь можно рассматривать как подграф. Цикл — это маршрут, концевые вершины которого совпадают, то есть маршрут, конец которого совпадает с его началом: отправился из одной вершины, прошёл несколько других вершин, вернулся в ту же вершину.

Теперь вы немного осведомлены об основных понятиях теории графов. Желаете продолжения этого математического банкета?

Ниже — задачи для математически настроенных читателей. Присылайте ваши решения в комментарии!

1. Докажите, что в любом графе сумма степеней вершин вдвое больше количества рёбер.

2. Докажите, что в любом графе количество рёбер не превышает количества сочетаний по 2 из n.

3. Выведите формулы для вычисления:

а) количества подграфов n-полного графа;

б) количества маршрутов n-полного графа;

в) количества путей n-полного графа;

г) количества циклов n-полного графа.

Источник: vk.com

Комментарии: