Теорема: Сумма степеней вершин графа равна удвоенному числу его ребер.

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

Опр. Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в ней ребер нечетно.

 

Полустепенью исхода вершины v орграфа G называется число 6 (v) дуг исходящих из вершины v (т.е. v является началом этих дуг).

Полустепенью захода вершины v орграфа G называется число 6 (v) дуг входящих в вершину v (т.е. v является концом этих дуг).

Замечание. В случае неориентированного псевдографа вклад каждой петли при расчете степени инцидентной вершины равен 2.

Пример 1. Рассмотрим ориентированный псевдограф, изображенный на рис.1.1.1.

а: d-(1)=2, d⁺(1)=2, d-(2)=0, d⁺(2)=1.

Пример 2. Рассмотрим неориентированный псевдограф, изображенный на рис.1.1.1.

а: d(1)=4, d(2)= 1, d(3)=1.

 

 

1. Маршруты, пути, циклы, связность.

 

Пусть G=(V,E) граф с p вершинами и q ребрами, т.е.

V={v1,v₂,…,v_p}, E={e1,e₂,…,e_q}.

Опр. Последовательность ребер, ведущая от некоторой вершины к другой, образует маршрут.

Опр. Маршрут называется цепью, если каждое ребро графа встречается в нем не более одного раза (вершины в цепи могут повторяться  несколько раз)

1. Две цепи из трех разных ребер:

2. Три разные ребра, из которых нельзя образовать цепь:

Опр. Цепь называется простой, если ее вершины различны, кроме, может быть первой и последней.

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

Пример:

Дан граф G.

 х₁ x₂ х₃ х₆ х₇ х₂— Маршрут длины 6, соединяющий вершины v1 и v2.

 х₁ x₂ х₃ х₆ х₇ х₂ х₁— замкнутый маршрут длины 7. Он начинается и заканчивается в вершине v1.

х₁ x₂ х₃ х₆ х₇  — цепь длины 5 (все ребра в ней различны). Эта цепь не является простой, так как при обходе вершину v₃ мы посетили два раза.

х₁ x₂ х₃ — пример простой цепи (все вершины на нашем пути были различны).

х₆ х₇ х₈ х₃ — цикл.

х₇ х₆ х₃ — простой цикл.

Опр. Граф без циклов называется ациклическим.

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

Опр. Две вершины графа называются связными, если существует соединяющая их простая цепь. В противном сл. две вершины графа называются несвязными.

Опр. Граф называется связным, если каждые две вершины его связные; Граф называется несвязным, если хотябы две его вершины несвязные.

Опр. Подграфом графаG называется граф, у которого все вершины и ребра принадлежат G. Если G1 – подграф графа G, то G называется надграфом графа G1.

Опр. Остовный подграф - это подграф графа, содержащий все его вершины.

Опр. Ребро, после удаления которого граф из связного превращается в несвязный, называется мостом.

---

Дата добавления: 2022-01-22; просмотров: 46; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!