Задачи для самостоятельного решения.

1. Определить вершинное число независимости и число вершинного покрытия графа G = < V, U >, у котрого V = {1,2,3,4,5,6,7},

U= {(1,2),(1,6),(1,7),(2,3),(3,4), (3,7), (4,5), (4,7), (5,6), (6,7)}. Показать

множество вершин графа G , соответствующих найденному числу

вершинного покрытия.

2. Определить реберное число независимости и число реберного

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

3. Определить вершинное число внешней устойчивости графа G = <V,U>,

у которого V = {1,2,3,4,5,6}, U= {(1,2),(1,6),(2,3), (2,5), (2,6), (3,4),

(3,5), (4,5), (5,6) }.

4. Определить реберное число внешней устойчивости графа G, заданного

в задаче 3.

5. Определить положительное и отрицательное вершинное число

внешней устойчивости ориентированного графа G = < V, U >, у

котрого V = {1,2,3,4,5,6}, U= {(1,2),(1,6),(2,6),(3,5), (4,3), (5,2), (5,4),

(6,5)}.

6. Определить плотность графа G = < V, U >, у котрого V =

={1,2,3,4,5,6,7}, U= {(1,2),(1,7),(2,3),(2,4), (2,5), (2,7), (3,4),(4,5), (4,7),

(5,6), (5,7),(6,7)}.

7. Найти максимальный поток через сеть G, если известна пропускная

способность дуг:

a = (v_1, v₂)-3, b= (v_1, v₃)-2, c = (v_1, v₄)-4, d= (v_3, v₄)-2,

e = (v_2, v₅)-3, f = (v_2, v₇)-5, g = (v_4, v₆)-4, h = (v_4, v₇)-1,

k = (v_5, v₈)-5, m = (v_6, v₈)-3, n = (v_6, v₉)-2, p = (v_7, v₉)-5,

r = (v_5, v₁₀)-6, s = (v_8, v₁₀)-4, t = (v_9, v₁₀)-2.

2. Раскраска вершин и ребер графа.

2.1. Понятие раскраски вершин и ребер графа

Под раскраской вершин графа понимают разбиение множества его

вершин на классы. Каждый класс состоит из вершин, имеющих некоторое общее свойство. Эти свойства могут быть «графовыми»: иметь одинаковую степень, одинаковое расстояние от фиксированной вершины, в двудольном графе вершины каждого подмножества составляют класс. В других случаях разбиение определяется свойствами объектов, описываемых при помощи графов. Например, структурная формула химического соединения - это граф, в котором соответствуют атомам молекулы химического соединения, ребра – валентным связям, а классы состоят из вершин, соответствующих атомам одного и того же элемента (рис.2.1).

н н н а а а

н N c c o н a b d d e a

н н а а

a,b,d,e - краски

Рис. 2.1 Рис. 2.2

Если теперь каким-либо образом отметить вершины,

принадлежащие одному и тому же классу (раскрасить в один цвет), то получится граф, который может соответствовать не только структурной формуле химического соединения, но каким-либо другим объектам (рис. 2.2). Главное, что одинаково отмеченные (раскрашенные в один цвет) вершины определяют одни и те же свойства того или иного объекта.

Аналогичным образом говорят о раскраске ребер графа и вообще о

раскраске элементов произвольного множества.

Часто рассматривают не произвольные раскраски вершин (ребер)

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