Лабораторная работа по "Программированию"

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

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

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

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

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

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

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

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