МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ

УНИВЕРСИТЕТ

СЕВЕРОДОНЕЦКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА»

(ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, ЧАСТЬ ІІ)

Северодонецк СТИ 2001

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ

УНИВЕРСИТЕТ

СЕВЕРОДОНЕЦКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА»

(ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, ЧАСТЬ ІІ)

для студентов всех форм обучения специальностей «Компьютерные системы и сети», «Системное программирование»

Северодонецк СТИ 2001

Методические указания к практически занятиям по курсу «Дискретная математика» (элементы теории графов, часть II) для студентов всех форм обучения специальностей «Компьютерные системы и сети», «Системное программирование» (Сост. А.Е. Богданов, - Северодонецк : СТИ, 2001 . – 49 с.

Составитель А.Е. Богданов

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

Устойчивость, порытия, паросочетания

1.1. Основные определения

Множество вершин графа называется внутренне устойчивым, если они попарно не смежны.

Внутренне устойчивое множество вершин графа называется пустым подграфом, если при добавлении хотя бы одной вершины, не принадлежащей этому множеству, образуется хотя бы одно ребро (дуга).

Пример 1. В графе G (рис.1.1) выделить внутренне устойчивое множество вершин и пустой подграф.

1

2 6

3. 5

4

G

Рис. 1.1

Внутренне устойчивыми множествами вершин для графа G являются множества вершин {1,3,5} и {1,3}, указанные на рис. 1,2 а, б. Внутренне устойчивое множество вершин {1,3,5} является пустым подграфом, т.к. добавление любой вершины графа G, не вошедшей в множество {1,3,5}, приводит к образованию ребер. Например, добавление вершины 4 приводит к образованию ребер (3,4) и (4,5) (рис.1.2в). Внутренне устойчивое множество вершин {1,3} не является пустым подграфом, т.к. добавление вершины 5 не приводит к образованию ребра (рис.1.2г).

1 1

m

3 5 3

а) б)

1

3 5

3 4 5

в) г)

Рис. 1.2 ■

Максимальная мощность пустого подграфа графа G называется числом внутренней устойчивости или вершинным числом независимости ε₀(G) графа G.

Максимальное число попарно несмежных ребер графа G называется реберным числом независимости ε₁(G) графа G.

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

Аналогично, множество ребер, покрывающих все вершины графа G, называются реберным покрытием графа. Минимальн6ая мощность реберного покрытия графа G называется числом реберного покрытия π₁(G).

Условимся считать, что любая вершина графа покрывает сама себя и две смежные вершины покрывают друг друга. Тогда минимальная мощность множества вершин, покрывающих все вершины графа G, называется вершинным числом внешней устойчивости графа β₀(G).

Аналогично будем считать что каждое ребро графа покрывает себя и два смежных ребра покрывают друг друга. Тогда минимальная мощность множества ребер, покрывающих все ребра графа G, называется реберным числом внешней устойчивости β₁(G).

Теорема 1.1. Для любого нетривиального связного графа G = < V, U > ε₀(G) + π₀(G) = ε₁(G) + π₁(G) = |V| . (1.1)

Множество ребер графа, в котором низкая пара ребер не смежна, называется паросочетанием графа.

Множество ребер паросочетания, в котором число ребер равно ε_1, называется наибольшим паросочетанием графа.

Теорема 1.2. Для двудольного графа G число ребер в наибольшем паросочетании равно числу вершинного покрытия, т.е. ε_{1 =} π₀.

Окрестностью G ( v₀) вершины v₀ графа G = < V, Г > называется подграф <V₀, U₀>, носитель которого совпадает с окрестностью единичного радиуса этой вершины, V₀=Гv_0,

а сигнатуру U₀ образуют все ребра графа G, соединяющие вершины из V_0.

Неокрестностью (v₀) вершины v₀ графа G = < V, Г > называется подграф

<V₀, U₀>, носитель которого V_{0 = {} v_{i /} v_i Гv_{0 }}, сигнатура U₀ состоит из всех ребер графа G, соединяющих вершины из V_0.

Пример 2. Указать G( v₀) и ( v₀) вершины v₀ графа G, изображенного на рис. 1.3.

v₉

v₈

v₁ v₇

v₂

v₃

v₆

v₀

v₄ v₅

G

Рис. 1.3

С огласно определению G( v₀) = <V₀, U₀>, где V₀=Гv_0, а U₀ – ребрf графа G, соединяющие из вершины V_0.

Значит, V₀=Гv₀= ₌ { v_1, v₂ , v_3, v₄}, U_{0 = =} { (v_1, v₂) , ( v_2, v₃)_, , ( v_3, v₄), }, (рис. 1.4а).

Согласно определению ( v₀) = <V₀, U₀>, где V_{0 =} { v_i / v_i Гv₀ }, а U₀ – ребрa графа G, соединяющие вершины из V_0. Значит,

V₀= { v_5, v₆ , v_7, v_8, v₉ }, U_{0 = =} { (v₅, v₆) , ( v_7, v₈)_, , ( v_8, v₉) } (рис. 1.4 б)

v₁

v₂ v₉

v₈

v₃ ( v₀) v₇

G( v₀)

v₆

v₄

v₅

а) б)

Рис. 1.4