Консультация № 183352
25.05.2011, 16:54
76.66 руб.
26.05.2011, 17:49
0 1 1
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Задан неориентированный граф без пятель из пяти вершин строками полуматрицы смежности в виде шестнадцатеричного числа, где первая цифра - первая строка полуматрицы, вторая цифра - вторая строка и т.д. Изобразить по заданному шестнадцатеричному числу граф в виде рисунка и определить степени всех вершин, цикломатическое и хронометрическое число. Изобразить ориентированный гра из четырех вершин по тому же числу, но полагать, что каждая цифра - строка матрицы смежности орграфа.
Число В331

Обсуждение

давно
Профессор
230118
3054
26.05.2011, 17:35
общий
это ответ
Здравствуйте, Евгений!

Цикломатическое число графа — минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим. Существует соотношение:
p1(G) = p0(G) + | E(G) | ? | V(G) | , где p1(G) — цикломатическое число, p0 — число компонент связности графа, | E(G) | — число рёбер, а | V(G) | — число вершин.
Имеем p0=1
| E(G) | =8
| V(G) | =5
p1(G)=1+8-5=4

хронометрическое число - такого не существует, а существует хроматическое число.
Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета.
Хроматическое число данного графа 4.


Ориентированный граф
Прикрепленные файлы:
Форма ответа