Логотип Автор24реферат
Задать вопрос
%
уникальность
не проверялась
Решение задач на тему:

Дан граф G=V E Граф G=V E – математический объект

уникальность
не проверялась
Аа
2739 символов
Категория
Высшая математика
Решение задач
Дан граф G=V E Граф G=V E – математический объект .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Дан граф: G=V,E Граф G=V,E – математический объект, состоящий из двух множеств. Одно из них (множество вершин VG) – любое конечное множество, его элементы называются вершинами графа: VG=1;2;3;4;5;6 число вершин: nG=6 Другое множество состоит из пар вершин, эти пары называются ребрами (множество ребер EG) графа, соединяющих пары вершин: EG=12;14;15;25;34;36;45;56 число ребер: mG=8 Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными: 12∩14∩15 для вершины 1 2;4;521∩25 для вершины 2 1;534∩36 для вершины 3 4;6 41∩43∩45 для вершины 4 1;3;551∩52∩54∩56 для вершины 5 1;2;4;663∩65 для вершины 6 3;5 Определить хроматическое число графа.

Нужно полное решение этой работы?

Ответ

Хроматическое число графа: χG=3

Решение

Потяни, чтобы посмотреть
Хроматическое число. Это понятие относится к неориентированным графам.
Граф называют r-хроматическим, если его вершины можно раскрасить r-различными цветами так, что никакие две смежные вершины не будут закрашены в один цвет.
Наименьшее число r, для которого граф является r-хроматическим, называется хроматическим числом неориентированного графа и обозначается через χG.
Нужно выбрать вершину максимально связанную с другими, то есть имеющую наибольшую степень –для всех связанных с ней вершин ее цвет заведомо использоваться не может.
deg1=3
deg2=2
deg3=2
deg4=3
deg5=4→max
Вершина 5 окрашивается в «синий цвет – цвет 1».
Все вершины графа смежные с вершиной a, не могут быть окрашены в «синий цвет – цвет 1».
Затем возвращаемся к первой в списке неокрашенных вершин, имеющую наибольшую степень . Просматривается список вершин сверху вниз
deg1=3→max
deg2=2
deg3=2
deg4=3→max
Выберем верхнюю вершин 4:
Окрашиваем ее в «зеленый цвет – цвет 2»
50% задачи недоступно для прочтения
Переходи в Кампус, регистрируйся и получай полное решение
Получить задачу
Больше решений задач по высшей математике:

Доказать что функция ux y=e-ysinx есть решение уравнения

836 символов
Высшая математика
Решение задач
Все Решенные задачи по высшей математике
Закажи решение задач
Оставляя свои контактные данные и нажимая «Найти работу», я соглашаюсь пройти процедуру регистрации на Платформе, принимаю условия Пользовательского соглашения и Политики конфиденциальности в целях заключения соглашения.

Наш проект является банком работ по всем школьным и студенческим предметам. Если вы не хотите тратить время на написание работ по ненужным предметам или ищете шаблон для своей работы — он есть у нас.