Учебное пособие: Дискретная мат-ка_УП

161

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

(4,6), (3,4), (5,6),  (2,7),  (3,7),(6,7),(1,5)}. 

Нарисуйте

его

, 

двойственный

ему

граф

, 

постройте

граф

, 

изоморфный

исходному

, 

матрицу

расстояний

, 

задайте

списком

смежности

. 

2. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2), 

(x1,x3), (x2,x3), (x2,x4), (x3,x4), (x3,x5),(x4,x4),(x4,x5)}. 

Постро

-

ить

его

графическое

представление

и

матрицы

инциденций

и

смежности

, 

все

простые

цепи

и

циклы

. 

3. 

Постройте

граф

 G=(X,U), |X| =n, |U|=m. n=7, m=13. 

Задай

-

те

его

с

помощью

матриц

смежности

и

инциденций

. 

Постройте

схему

алгоритма

перехода

от

одной

матрицы

к

другой

. 

 
Вариант №5 
1. 

Задан

граф

 G=(X,U),  

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

(1,3), (2,5),  (6,8), (5,6),  (1,9), (9,3), (2,7), (7,7), (3,7)}. 

2. 

Нарисуйте

его

, 

двойственный

ему

граф

,  

дайте

полную

характеристику

  (

связность

, 

циклы

, 

ориентированность

, 

матрица

расстояний

и

т

.

д

.), 

задайте

матрицей

смежности

. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5},U={(x1,x2), (x1,x3), 

(x2,x3), (x2,x4), (x3,x4), (x3,x5),(x4,x4),(x4,x5)}. 

Построить

его

графическое

представление

и

матрицы

инциденций

и

смежности

, 

все

простые

цепи

и

циклы

. 

3. 

Подсчитайте

число

суграфов

, 

включая

изоморфные

, 

в

графе

 G=(X,U), |X| =n. 

 
Вариант №6 
1. 

Задан

граф

 G=(X,U),  

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

(1,3), (2,5),  (6,8), (5,6),  (1,9), (9,3), (2,7),  (7,7), (3,7)}. 

2. 

Нарисуйте

его

, 

двойственный

ему

граф

,  

найдите

подграф

, 

суграф

, 

дополненние

до

полного

графа

, 

постройте

матрицу

рас

-

стояний

, 

определите

диаметр

графа

. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x6,x6}, U={(x4,x1), 

(x1,x2), (x2,x6), (x6,x5),(x2,x3),(x3,x5),(x5,x2)}. 

Построить

рас

-

краску

графа

и

найти

его

хроматическое

число

. 

162

3. 

Подсчитайте

число

суграфов

, 

включая

изоморфные

, 

в

графе

 G=(X,U), |X| =n. 

 
Вариант №7 
1.

Задан

граф

 G=(X,U),  

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

(4,6), (3,4), (5,6),  (2,7),  (3,7),(6,7),(1,5)}. 

Нарисуйте

его

, 

двойственный

ему

граф

, 

задайте

матрицей

инциденций

, 

постройте

подграф

, 

суграф

, 

дополнение

до

полного

графа

, 

определите

диаметр

графа

и

его

хроматическое

число

. 

2. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5,x6}, U={(x1,x2), 

(x2,x4), (x4,x3), (x1,x1), (x3,x6), (x3,x2), (x1,x5), (x3,x1), (x6,x5), 
(x6,x1), (x3,x5), (x5,x4)}.

Постройте

граф

. 

Найдите

минимальное

покрывающее

его

дерево

. 

Вес

вершин

 2,6,4,2,5,4,7,9,2,4,6,4 

соот

-

ветственно

. 

3. 

Предложите

методы

построения

графов

с

эйлеровыми

и

гамильтоновыми

циклами

на

заданных

наборах

вершин

и

ребер

. 

 
Вариант №8 
1. 

Задан

граф

 G=(X,U),  

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

(1,3), (2,5), (4,6),  (5,6), (4,8), (1,9), (9,3), (1,7), (7,4), (3,7)}. 

2. 

Нарисуйте

его

, 

двойственный

ему

граф

, 

задайте

матрицей

инциденций

, 

смежности

, 

найдите

эйлеров

цикл

, 

гамильтонов

цикл

, 

постройте

плоский

и

планарный

граф

. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2), 

(x2,x4), (x4,x3), (x1,x1), (x3,x4), (x3,x2), (x1,x5), (x3,x1), (x5,x5), 
(x2,x1), (x3,x5), (x5,x4)}. 

Постройте

его

, 

найдите

все

простые

це

-

пи

.  

3. 

Предложите

алгоритм

построения

двудольных

графов

с

заданным

числом

вершин

. 

Вариант №9  
1. 

Задан

граф

 G=(X,U), 

X={1,2,3,4,5}, U={(1,3),(2,4),(5,1)(3,5),(5,4)(1,4)}. 

Нарисуйте

его

, 

задайте

матрицу

смежности

и

инциденций

, 

нарисуйте

двойственный

ему

граф

и

для

него

задайте

матрицы

163

смежности

и

инциденций

, 

найдите

диаметр

графа

и

его

хромати

-

ческое

число

. 

2. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2), 

(x2,x4), (x4,x3), (x1,x1), (x3,x4), (x3,x2), (x1,x5), (x3,x1), (x5,x5), 
(x2,x1), (x3,x5), (x5,x4)}. 

Построить

граф

. 

Найдите

минимальное

покрывающее

его

дерево

. 

Вес

вершин

 2,1,4,2,7,4,7,3,2,4,6,4 

соот

-

ветственно

. 

3. 

Определите

хроматическое

число

неполного

связного

графа

 G=(X,U), |X| =n, |U|=m. n=8, m=18. 

Вариант №10 
1. 

Задан

граф

 G=(X,U), 

X={1,2,3,4,5}, U={(1,3),(2,4),(2,1)(3,5),(5,4)(1,4),(4,4)}. 

Нарисуйте

его

, 

задайте

матрицу

смежности

и

инциденций

, 

нарисуйте

двойственный

ему

граф

и

для

него

задайте

матрицы

смежности

и

инциденций

, 

постройте

плоский

и

планарный

граф

. 

2. 

Дайте

определение

Эйлерова

графа

. 

Приведите

пример

. 

Будет

ли

граф

 G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2), (x2,x3), 

(x2,x5), (x3,x4), (x1,x4), (x3,x5)} 

Эйлеровым

? 

Нарисуйте

его

. 

По

-

стройте

минимальный

цикл

.  

3. 

Постройте

произвольный

граф

 G=(X,U), |X| =n, |U|=m. 

n=10, m=18. 

Определите

его

цикломатическое

число

. 

Укажите

,  

какие

ребра

должны

быть

удалены

из

графа

, 

чтобы

он

стал

ацик

-

лическим

. 

Вариант №11 
1. 

Задан

граф

 G=(X,U), 

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

Нарисуйте

его

, 

задайте

матрицу

смежности

и

инциденций

, 

нарисуйте

двойственный

ему

граф

и

для

него

задайте

матрицы

смежности

и

инциденций

, 

нарисуйте

изоморфный

ему

граф

, 

оп

-

ределите

его

диаметр

. 

2. 

Задан

граф

. 

Найдите

минимальное

покрывающее

его

де

-

рево

. G=(X,U), X={x1,x2,x3,x4,x5,x6,x7}, 

U={(x1,x3)(x1,x2)(x1,x4)(x2,x3)(x2,x6)(x2,x5)(x3,x4)(x3,x7)(x4,x5) 
(x4,x6)(x1,x6)(x7,x6)}. «

Вес

» 

ребер

равен

: 4,3,1,6,1,4,5,2,7,8,1,9 

соответственно

. 

164

3. 

Определите

множество

полных

графов

, 

содержащих

од

-

новременно

эйлеровы

и

гамильтоновы

циклы

. 

Вариант №12 
1. 

Задан

граф

 G=(X,U), 

X={1,2,3,4,5}, U={(2,4),(5,1)(3,5),(5,5)(1,4)}. 

Нарисуйте

его

, 

задайте

матрицу

смежности

и

инциденций

, 

нарисуйте

двойственный

ему

граф

и

для

него

задайте

матрицы

смежности

и

инциденций

. 

Для

исходного

графа

нарисуйте

планарный

и

плоский

граф

, 

определите

его

хроматическое

число

. 

2. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4}, U={(x1,x2), (x1,x3), 

(x2,x3), (x2,x4), (x3,x4), (x1,x4),(x4,x4)}. 

Построить

все

простые

цепи

из

Х

1 

в

Х

3. 

3.

Доказать

, 

что

среди

любых

 6 

человек

есть

либо

 3 

попарно

знакомых

, 

либо

 3 

попарно

незнакомых

. 

Вариант №13 
1. 

Задан

граф

 G=(X,U), 

X={1,2,3,4,5}, U={(1,3),(3,4),(5,2)(3,5),(5,4)(1,4)}. 

Нарисуйте

его

, 

задайте

матрицу

смежности

и

инциденций

, 

нарисуйте

двойственный

ему

граф

и

для

него

задайте

матрицы

смежности

и

инциденций

. 

2.

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2), 

(x1,x3), (x2,x3), (x2,x4), (x3,x4), (x3,x5),(x4,x4),(x4,x5)}. 

Постро

-

ить

его

графическое

представление

, 

все

простые

цепи

и

циклы

. 

3. 

Описать

в

терминах

теории

графов

отношение

эквива

-

лентности

на

конечном

множестве

. 

 
Вариант №14 
1. 

Задан

граф

 G=(X,U),  

X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(2,4), <2,8>, <2,7>, <3,6>, 

(2,3), (1,3), (2,5), (4,6),  (5,6), <4,8>, <1,9>, <9,3>, (1,7),  (2,5), (7,4), 
(3,7), <7,2>, <8,3>, <3,6>}. 

Нарисуйте

его

,  

дайте

полную

характеристику

. 

2.

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x6,x5}, U={(x1,x2), 

(x2,x4), (x4,x3), (x1,x1), (x3,x5), (x3,x2), (x1,x5), (x3,x1), (x2,x5), 
(x6,x1), (x3,x5), (x5,x4)}. 

Дайте

определения

: 

маршрута

, 

цепи

, 

165

цикла

, 

связности

. 

Постройте

на

заданном

графе

маршрут

, 

цепь

, 

цикл

, 

покрывающее

его

дерево

. 

3. 

Доказать

, 

что

если

граф

связен

и

конечен

, 

то

поиск

в

ши

-

рину

и

поиск

в

глубину

обойдут

все

его

вершины

по

одному

разу

. 

Вариант №15 
1. 

Задан

граф

 G=(X,U),  

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

(6,1),(3,6).(2,1),(1,1)} 

Нарисуйте

его

,  

дайте

полную

характери

-

стику

, (

связность

, 

ориентированность

, 

матрица

расстояний

,  

хро

-

матическое

число

, 

планарность

и

т

.

д

.).  

2.

Дайте

определение

Эйлерова

графа

. 

Приведите

пример

. 

Будет

ли

граф

 G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2), (x1,x3), 

(x1,x2), (x2,x4), (x3,x4), (x3,x5) (

х

2,

х

5)} 

Эйлеровым

? 

Нарисуйте

его

. 

Постройте

минимальный

цикл

. 

3. 

Доказать

, 

что

граф

связен

тогда

и

только

тогда

, 

когда

его

нельзя

представить

в

виде

объединения

двух

графов

. 

Вариант №16 
1. 

Задан

граф

 G=(X,U),  

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

(1,3), (2,5), (4,6),  (5,6), (4,8), (1,9), (9,3), (1,7),  (2,5), (7,4), (3,7)}. 

Нарисуйте

его

,  

дайте

полную

характеристику

, (

связность

, 

циклы

, 

ориентированность

, 

матрица

расстояний

и

т

.

д

.) 

задайте

матрицей

смежности

. 

2.

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,

х

5}, U={(x1,x2), 

(x1,x3),(x2,x3),(x2,x4),(x3,x4),(x1,x4),(x4,x4),(

х

3,

х

5),(

х

5,

х

4),(

х

1,

х

5)}. 

Построить

все

простые

цепи

из

Х

2 

в

Х

5. 

3. 

Нарисовать

диаграммы

всех

деревьев

с

 7 

вершинами

. 

Вариант №17 
1. 

Задан

граф

 G=(X,U),  

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

(1,3), (2,5), (4,6), (3,4), (6,8), (5,6), (4,8), (1,9), (9,3), (2,7), (7,6), 
(4,3), (2,5), (7,7), (3,7)}. 

Нарисуйте

его

,  

дайте

полную

характеристику

  (

связность

, 

циклы

, 

ориентированность

, 

матрица

расстояний

и

т

.

д

.), 

задайте

матрицей

смежности

.