Неориентированный граф на 6 вершинах задан вектором Rmn (табл.1), где m и n –

Неориентированный граф на 6 вершинах задан вектором Rmn (табл.1), где m и n – номера вершин графа, m=1,2, 3,4,5,6 и n=1, 2, 3,4,5,6. Элементы вектора Rmn соответствуют количеству ребер между соответствующими вершинами m и n. Для заданного графа необходимо: 1) Выстроить матрицу смежности и матрицу инцидентности для заданного графа. Построить граф. 2) Найти тип графа. 3) Выписать все эйлеровые и гамильтоновые цепи и циклы (если есть). Ответ обосновать. 4) Определить хроматическое и реберное хроматическое число графа. 5) Раскрасить вершины (тремя способами) и ребра графа. Таблица 1 – Неориентированный граф m 1 1 1 1 1 2 2 2 2 3 3 3 4 4 5 n 2 3 4 5 6 3 4 5 6 4 5 6 5 6 6 Rmn 2 0 1 1 0 0 1 0 1 0 0 0 0 2 1

Построим геометрическое изображение заданного графа G (рис.1):
х1
e1
e2
e3
e4
e5
х2
х3
х4
х5
х6
e6
e7
e8
e9
х1
e1
e2
e3
e4
e5
х2
х3
х4
х5
х6
e6
e7
e8
e9
Рис.1 –  Граф G
Матрицей смежности неориентированного графа G(X,E) называется матрица A(G) n-го порядка (n – число вершин) с элементами:
Петля считается за два ребра.
Строим матрицу смежности для нашего графа:
.
Матрицей инцидентности неориентированного графа G(X,E) называется матрица В(G) размера nm (n – число вершин, m – число ребер) с элементами:
Строим матрицу инцидентности для графа G:
.
2) Граф является неориентированным. Поскольку в графе есть изолированная вершина х3, то граф является несвязным. Так как в графе есть кратные ребра, то он является мультиграфом. Граф можно разместить на плоскости таким образом, чтобы ребра не пересекались (рис.1), поэтому он является планарным.
3) Эйлеров граф – это граф, содержащий эйлеров цикл.
Полуэйлеров граф – это граф, содержащий эйлерову цепь.
Эйлеров путь (эйлерова цепь) в графе – это путь (путь в графе –последовательность вершин таких, что две любые последовательные вершины соединены хотя бы одной дугой (ребром)), проходящий по всем дугам (ребрам) графа и притом только по одному разу.
Эйлеров цикл – это эйлеров путь, являющийся циклом (цикл или контур – цепь, в котором последняя вершина совпадает с первой).
Кроме того, согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный и в нем отсутствуют вершины нечетной степени.
Наш граф состоит из двух компонент связности, одна из которых не содержит ребер (это вершина х3), а у второй все вершины – четной степени. Поэтому граф является эйлеровым и все его эйлеровы цепи являются одновременно и эйлеровыми циклами. Выпишем их все (указываем названия ребер):
1) е1 – е2 – е3 – е5 – е6 – е7 – е8 – е9 – е4;
2) е1 – е2 – е3 – е5 – е6 – е8 – е7 – е9 – е4;
3) е1 – е2 – е3 – е7 – е6 – е5 – е8 – е9 – е4;
4) е1 – е2 – е3 – е7 – е8 – е5 – е6 – е9 – е4;
5) е1 – е2 – е3 – е8 – е6 – е5 – е7 – е9 – е4;
6) е1 – е2 – е3 – е8 – е7 – е5 – е6 – е9 – е4;
7) е1 – е2 – е4 – е9 – е6 – е5 – е7 – е8 – е3;
8) е1 – е2 – е4 – е9 – е6 – е5 – е8 – е7 – е3;
9) е1 – е2 – е4 – е9 – е7 – е5 – е6 – е8 – е3;
10) е1 – е2 – е4 – е9 – е7 – е8 – е6 – е5 – е3;
11) е1 – е2 – е4 – е9 – е8 – е5 – е6 – е7 – е3;
12) е1 – е2 – е4 – е9 – е8 – е7 – е6 – е5 – е3;
13) е2 – е1 – е3 – е5 – е6 – е7 – е8 – е9 – е4;
14) е2 – е1 – е3 – е5 – е6 – е8 – е7 – е9 – е4;
15) е2 – е1 – е3 – е7 – е6 – е5 – е8 – е9 – е4;
16) е2 – е1 – е3 – е7 – е8 – е5 – е6 – е9 – е4;
17) е2 – е1 – е3 – е8 – е6 – е5 – е7 – е9 – е4;
18) е2 – е1 – е3 – е8 – е7 – е5 – е6 – е9 – е4;
19) е2 – е1 – е4 – е9 – е6 – е5 – е7 – е8 – е3;
20) е2 – е1 – е4 – е9 – е6 – е5 – е8 – е7 – е3;
21) е2 – е1 – е4 – е9 – е7 – е5 – е6 – е8 – е3;
22) е2 – е1 – е4 – е9 – е7 – е8 – е6 – е5 – е3;
23) е2 – е1 – е4 – е9 – е8 – е5 – е6 – е7 – е3;
24) е2 – е1 – е4 – е9 – е8 – е7 – е6 – е5 – е3;
25) е3 – е5 – е1 – е2 – е6 – е7 – е8 – е9 – е4;
26) е3 – е5 – е1 – е2 – е6 – е8 – е7 – е9 – е4;
27) е3 – е7 – е6 – е1 – е2 – е5 – е8 – е9 – е4;
28) е3 – е7 – е6 – е2 – е1 – е5 – е8 – е9 – е4;
29) е3 – е8 – е6 – е1 – е2 – е5 – е7 – е9 – е4;
28) е3 – е8 – е6 – е2 – е1 – е5 – е7 – е9 – е4;
29) е3 – е7 – е8 – е5 – е1 – е2 – е6 – е9 – е4;
30) е3 – е7 – е8 – е5 – е2 – е1 – е6 – е9 – е4;
31) е3 – е8 – е7 – е5 – е1 – е2 – е6 – е9 – е4;
32) е3 – е8 – е7 – е5 – е2 – е1 – е6 – е9 – е4;
33) е4 – е9 – е6 – е1 – е2 – е5 – е7 – е8 – е3;
34) е4 – е9 – е6 – е1 – е2 – е5 – е8 – е7 – е3;
35) е4 – е9 – е6 – е2 – е1 – е5 – е7 – е8 – е3;
36) е4 – е9 – е6 – е2 – е1 – е5 – е8 – е7 – е3;
37) е4 – е9 – е7 – е5 – е1 – е2 – е6 – е8 – е3;
38) е4 – е9 – е7 – е5 – е2 – е1 – е6 – е8 – е3;
39) е4 – е9 – е8 – е5 – е1 – е2 – е6 – е7 – е3;
40) е4 – е9 – е8 – е5 – е2 – е1 – е6 – е7 – е3
41) е4 – е9 – е7 – е8 – е6 – е1 – е2 – е5 – е3;
42) е4 – е9 – е7 – е8 – е6 – е2 – е1 – е5 – е3;
43) е4 – е9 – е8 – е7 – е6 – е1 – е2 – е5 – е3;
44) е4 – е9 – е8 – е7 – е6 – е2 – е1 – е5 – е3.
Гамильтонов граф – это граф, содержащий гамильтонов цикл