лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4

• Название: Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
• Анкор: лекции по дм
• Дата: 08.02.2021
• Размер: 1.51 Mb.
• Имя файла: лекции.docx
• Тип: Документы; #174835
• страница: 18 из 40

Элементы графов. Подграфы. Валентность.

После рассмотрения определений, относящихся к графам как к цельным объектам, естественно дать определения различным составным элементам графов.

Определение 9.6.Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G'), если V' включенов V и/или Е' включенов Е.

Определение 9.7.Если V' = V, то G' называется остовным подграфом G.

Определение 9.8.Если V' включенов V и Е' включенов Е (причем V' не равно Vи E' не равно E ), то граф G' называется собственным подграфом графа G.

Определение 9.9.Подграф G'(V',Е') называется правильным подграфом графа G(V,Е), если G' содержит все возможные ребра G. Правильный подграф G'(V, Е') графа G(V, Е) определяется подмножеством вершин V'.

Определение 9.10.Количество ребер, инцидентных вершине v, называется степенью (или валентностью вершины v) и обозначается d(v).

Причем 0  d(v) 1 d(v) = |Г(v)|.

Обозначим минимальную степень вершины графа G через (G), а максимальную — через (G).

Определение 9.11.Если степени всех вершин равны k, то граф называется регулярным степени k:

Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.

Пример: Ниже приведена диаграмма регулярного графа степени 3



Если степень вершины равна 0, то вершина называется изолированной. Если степень вершины равна 1, то вершина называется концевой, или висячей.

Для орграфа число дуг, исходящих из вершины v, называется полустепенъю исхода, а входящих – полустепенью захода. Обозначаются эти числа, соответственно, d^–(v) и d⁺(v).

Теорема Эйлера.

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

Для ориентированного графа: .

Доказательство: При подсчете суммы степеней вершин каждое ребро учитывается два раза для одного конца ребра и для другого.

Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети.

Маршруты в графах. Цепи. Циклы.

Определение 10.1. Маршрут – чередующаяся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны.

₁=v₀e₁v₁e₂v₂e₃…e_kv_k

Определение 10.2. Если v₀ = v_k, то маршрут называют цепью.

Определение 10.3. Если все вершины, а значит и ребра, различны, то маршрут называют простой цепью.

В этой цепи вершины v₀ и v_k называют концами цепи. Говорят, что цепь с концами u, v соединяет вершины u, v. Она обозначается . Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называют ацикличным. Для орграфов цепь называется путем, а цикл – контуром.

Пример:

v₁v₃v₁v₄ – маршрут,

v₁v₃v₅v₂v₃v₄ – цепь,

v₁v₄v₃v₂v₅ – простая цепь,

v₁v₃v₅v₂v₃v₄v₁ – цикл,

v₁v₃v₄v₁ – простой цикл.

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

Если маршрут =v₀e₁v₁e₂v₂e₃…e_kv_k, то длина маршрута равна k, ||=k, k – число ребер.