Задания

1. Построить граф G=(X, A), где Х={хi},  i=1,2,...,6, A={ai}, i=1,2,...,11, a1=(x1,x4), a2=(x2,x3), a3=(x2,x6), a4=(x3,x5), a5=(x3,x1), a6=(x4,x5), a7=(x4,x1), a8=(x5,x1) a9=(x4,x6), a10=(x6,x1), a11=(x6,x3).

Для графа G  найти  обратные многозначные отображения Г-1(х4), Г-2(х3) и т. д. Подсчитать полустепени исхода и захода d0(x4) и d t(x5) . Построить матрицы смежности и инцидентности для графа G. Найти прямое Т+(х1) и обратное Т-(х6) транзитивные замыкания. Построить порожденный подграф, включающий вершины x1, x2 ,x3, x6. Построить остовный подграф, включающий дуги (xi, x j), если i+j > 4. Найти все вершины, входящие в путь между вершинами  (х1 и х3 ) и ( х1 и х5).

2. Построить граф G=(X, Г), где X={xi}, i=1,2,...,6,

Г(х1)={х1,х3,х4},Г(х2)={х2,х4,х6},Г(х3)={х3,х6},Г(х4)={х5,х6},Г(х5)={х2,х6} Г(х6)={х1,х3}.

Для графа G  найти  обратные многозначные отображения Г-1(х1), Г-2(х1) и т. д. Подсчитать полустепени исхода и захода d0(x5) и d t(x4) . Построить матрицы смежности и инцидентности для графа G. Найти прямое Т+(х4) и обратное Т-(х5) транзитивные замыкания. Построить порожденный подграф, включающий вершины x1, x2 ,x3, x6. Построить остовный подграф, включающий дуги (xi, x j), если | i-j |> 2. Найти пару вершин, между которыми максимальное число путей длины 2.

3. Построить граф G=(X, Г), где X={xi}, i=1,2,...,6, Г(х1)={х2,х4}, Г(х2)={х2,х3,х5}, Г(х3)={х3,х6}, Г(х4)={х5},Г(х5)={х2,х5} Г(х6)={х1,х3}.

является ли он двудольным? Если нет, то какое минимальное число дуг необходимо убрать, чтобы он таковым стал? является ли граф антисимметрическим? Полным?

4. Построить граф G=(X, Г), где Х={хi},  i=1,2,...,6, A={ai}, i=1,2,...,11, a1=(x1,x2), a2=(x2,x3), a3=(x2,x5), a4=(x3,x5), a5=(x3,x1), a6=(x4,x5), a7=(x4,x1), a8=(x5,x1) a9=(x4,x6), a10=(x6,x1), a11=(x6,x3).

является ли он планарным? Если нет, то какое минимальное число дуг необходимо убрать, чтобы он таковым стал? построить орцепи максимальной длины из вершины  x4 и Гамильтоновы контуры, если возможно.

5.  Нарисовать граф - дерево из 9 вершин. Какими свойствами должна обладать матрица смежности такого графа?

6. Нарисовать произвольные графы полный и симметрический из 6 вершин (по два варианта каждого типа). Какими свойствами обладают матрицы смежности таких графов?

7. Разбить граф на максимальные сильно связные подграфы матричным способом. (матрица А)

  матрица А  матрица B

1	0	0	1	0	0	1	0	0	6	9	3	0	4	0	0
0	0	0	0	1	0	0	1	6	0	0	8	0	15	0	0
0	0	0	0	0	1	0	0	9	1	0	2	5	0	13	0
1	0	0	0	0	0	1	0	0	8	2	0	16	0	3	0
0	1	0	0	1	0	0	1	0	0	5	16	0	0	0	4
0	0	1	0	0	1	0	0	4	15	0	0	0	0	7	0
1	1	0	0	0	0	0	0	0	0	13	0	0	7	0	3
0	0	0	0	1	0	0	0	0	0	0	0	4	0	0	0

8.  Построить базу относительно вершины х6 по матрице В.

9. Разбить граф на максимальные сильно связные подграфы, начиная с x4. (матрица С)

  матрица С  матрица D

0	0	0	1	0	0	0	0	0	4	3	0	4	0	0
0	0	0	0	1	0	0	1	4	0	0	8	0	15	0	0
0	0	0	0	0	1	0	0	9	1	0	2	5	0	13	0
1	0	0	0	0	0	1	0	0	8	2	0	16	0	3	0
0	1	0	0	1	0	0	1	0	0	5	16	0	0	0	4
0	0	1	0	0	1	0	0	4	15	0	0	0	0	7	0
1	1	0	0	0	0	0	0	0	0	13	0	0	7	0	3
0	0	0	0	1	0	0	0	0	0	0	0	4	0	0	0

10. Построить базу относительно вершины х6 по матрице D.