Контрольная работа №3

1

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)}

Нарисуйте его, дайте полную характеристику: связность, циклы, цепи, маршруты, ориентированность, постройте матрицу расстояний, задайте матрицей смежности.

2. Построить минимальное покрывающее дерево для графа, заданного таблицей:

	X1	X2	X3	X4	X5	X6	X7
X1	0	0	2	2	1	0	4
X2	0	0	3	0	1	2	0
X3	2	3	0	5	4	0	5
X4	2	0	5	0	2	3	0
X5	1	1	4	2	0	0	0
X6	0	2	0	3	0	0	5
X7	4	0	5	0	0	5	0

Здесь нулем кодируется отсутствие смежности вершин, цифрой - вес соответствующих ребер.

3. Постройте схему алгоритма выделения из графа суграфа и подграфа с заданным числом ребер.

2

1.Задан граф G=(X,U),

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

Нарисуйте его, задайте матрицей смежности постройте подграф, суграф, плоский и планарный

2. Рассчитайте длины всех проводников заданных решетчатым графомG=(X,U), X={x3,x15,x12,x23) U={(x3,x15),(x15,x23),(x23,X3),(x23,x12).

3. Для полного графа с 4 вершинами постройте все покрывающие неизоморфные деревья

3

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}, U={(x1,x2), (x1,x3), (x2,x3), (x2,x4), (x3,x4), (x1,x4),(x4,x4)}. Построить простую цепь из Х2 в Х3.

3. Постройте произвольный мультиграф G=(X,U), |X| =n, |U|=m. N=8,m=14

определите его мультичисло.

4

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}, 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)}. Построить раскраску графа и найти его хроматическое число.

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)}

Нарисуйте его, задайте матрицу смежности и инциденций, нарисуйте двойственный ему граф, и для него задайте матрицы смежности и инциденций, найдите диаметр графа и его хроматическое число.

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 соответственно.

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.

2. Доказать, что среди любых 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)}. Дайте определения: маршрута, цепи, цикла, связности. Постройте на заданном графе маршрут, цепь, цикл, покрывающее его дерево

3. Доказать, что если граф связен и конечен. То поиск в ширину и поиск в глубину обойдут все его вершины по одному разу.

26

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. Дайте определение Эйлерова грfфа. Приведите пример. Будет ли граф 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. Доказать, что граф связен тогда и только тогда когда его нельзя представить в виде объединения двух графов.

15

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 вершинами.

16

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)}

Нарисуйте его, дайте полную характеристику, (связность, циклы, ориентированность, матрица расстояний и т.д.) задайте матрицей смежности.

2. Задан граф G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x4), (x1,x3), (x2,x1), (x2,x4), (x3,x4), (x3,x5),(x4,x4),(x4,x5)}. Построить его графическое представление и матрицы инциденций и смежности, все простые цепи.

3. Доказать, что полный граф имеет n^n-2 деревьев.

17

1. Задан граф G=(X,U),

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

Нарисуйте его, дайте полную характеристику (связность, циклы, ориентированность, матрица расстояний и т.д.), задайте матрицей смежности

2. Задан граф G=(X,U), X={x1,x2,x3,x4,x5,x6}, U={(x1,x2), (x2,x4), (x4,x6), (x1,x1), (x3,x6), (x3,x2), (x1,x5), (x3,x1), (x6,x5), (x6,x1), (x2,x5), (x5,x4)}.Постройте граф. Найдите раскраску графа. Начиная с 1 вершины и с 5 .

3. Построить сеть Петри для решения задачи о 5 мудрецах. (5 мудрецов. Могут есть или думать. Для еды им даны 5 палочек. Чтобы поесть, мудрецу нужны 2 палочки.)

18

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,х6}, 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),(х1,х6), (х2,х6)}. Постройте его, найдите все простые цепи из 3 в 6 вершину.

3. Показать, что граф, имеющий мост, не является эйлеровым.

19

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,x6,x5}, U={(x1,x2), (x2,x3), (x4,x3), (x5,x1), (x3,x6), (x3,x2), (x1,x5), (x3,x1), (x6,x5), (x6,x1), (x3,x5), (x5,x4)}. Дайте определения: маршрута, цепи, цикла, связности. Постройте на заданном графе маршрут, цепь, цикл, покрывающее его дерево

3. определить число неизоморфных деревьев двудольного графа К_2,3.

20

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. Дайте определение цикла, маршрута. Приведите пример, используя граф заданный таблицей:

	X1	X2	X3	X4	X5
X1	0	1	1	0	1
X2	1	0	1	0	0
X3	1	1	0	1	1
X4	0	0	1	0	1
X5	1	0	1	1	0

Найдите хроматическое число и диаметр заданного графа.

3. Доказать, что удаление одного ребра, которое принадлежит какому-то циклу связного графа, не делает этот граф несвязным.

21

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|=6 (6 вершин) и степень каждой вершины   3. Нарисовать такой граф и построить все его простые циклы.

3. доказать, что эйлеров граф не имеет мостов.

22

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. Дайте определение и назначение решетчатого графа. Приведите пример основных соотношений. Найдите расстояние между вершинами x5 и x27 (решетку взять из лекций).

3. Построить примеры графов, для которых алгоритм последовательного раскрашивания строит не минимальную раскраску.