Теория Графов. Часть 2 Смежность, инцидентность, петли

Ничего не сделано, если что-то осталось недоделанным. – Иоганн Гаусс

В этой статье:

• Смежность и инцидентность

• Петли

Смежность и инцидентность

Давайте рассмотрим самый обыкновенный неопределённый граф (Рисунок 1). В нем есть вершина Р и вершина К. Данные вершины являются смежными (adjacent), так как они соединены ребром РК.

Помимо этого, как мы видим, вершина К является концом ребра РК, а Р его началом, в таких случаях вершина К и Р называются инцидентными (incident) ребру РК.

Смежностью вершин графа – называется отношение между двумя вершинами, в котором существует ребро их соединяющее.

Инцидентность – это когда вершина a является началом или концом ребра t. Если мы добавим еще одну вершину b, то мы скажем, что вершина a и b инцидента ребру t.

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

Смежностью рёбер графа – называется отношение между двумя рёбрами, в котором существует вершина соединяющая их.

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

В ориентированном графе все немного по-другому (Рисунок 2), так у нас имеется направление, которое мы не в силах поменять. Если вершина 1 смежна вершине 2, то вершина 2 не может быть смежна вершине 1. То же самое касается и инцидентности. Вершины 1 и 2 инцидентны ребру 12, наоборот не работает.

Петли

Петля – это ребро инцидентное одной и той же вершине. То есть вершина которая соединена сама с собой. На рисунке ниже мы видим, как это выглядит.

Заключение

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

P.S. Если вам показалось, что эта статья была очень, очень подробной или раздутой, то сообщите об этом в комментариях, так как в своих статьях я стремлюсь к тому, чтобы люди читающие их смогли понять описываемую мною тему. Неточности и предложения о темах также пишите в комментарии.