Ви є тут

Основные понятия теории графов, часть 1

Граф G — это совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами. 

История

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

Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуть­ся в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра — с мостами, которыми связаны эти части.

Эйлеру удалось доказать, что искомого маршрута обхода города не существует.


Неориентированным графом  G(VE) называется совокупность двух множеств: не пустого множества V (множества вершин) и множества E - множество неупорядочных  пар элементов из V  (множества ребер).

Пусть v и u вершины графа,  e = (vu) это ребро графа, тогда вершина v и ребро e u называются инцидентными, вершина u и ребро e так же инцидентные.

Два ребра инцидентные одной вершине называются смежными.

Две вершины инциденты одному ребру называются смежными.

Степенью или валентностью вершины называется количество ребер инцидентности этой вершины d(V).

Минимальная степень графа (G).

Максимальная степень графа (G).

Регулярным графом  степени k называется граф, степени всех вершин которого равны k .

Вершина называется изолированной, если ее степень равна 0.

Вершина называется висячей, если ее степень равна 1.

Петлей называется ребро, начинающееся  и заканчивающееся в одной вершине.

Кратными ребрами называется ребра инцидентные одной и той же паре вершин.

Простым графом  называется граф без петель и кратных ребер с конечным количеством вершин.

Граф называется полным, если любая пара вершин соединена одним ребром.


Маршруты, цепи, циклы

Маршрутом в графе  называется  последовательность   вершин  и ребер  v0 v1 v2 v3 …vn.

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

Маршрут, в котором все вершины различны, называется простой цепью.

Замкнутая простая цепь называется простым циклом.

Замкнутая цепь называется циклом.

Расстоянием между вершинами u и v  называется длина кратчайшей цепи d(uv).

Кратчайшая цепь, соединяющая вершины называется геодезическая.

Диаметром графа G называется длина длиннейшей геодезической цепи.

Источник urtt.ru

теория графов

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer