Хроматическое число и хроматический индекс графов

@javavirys · Регистрация: 07.11.2013

Author24 — интернет-сервис помощи студентам

Найдите хроматическое число и хроматический индекс графов:

Вычислил степени всех вершин:
deg1=3,deg2=3,deg3=3,deg4=3,deg5=3,deg6=3
А дальше что-то не пойму, с раскрасками

@AdmiralHood · 14.04.2014, 13:33

У треугольника хроматическое число 3. Ваш граф - это два треугольника, соответственные вершины которых соединены рёбрами. Два треугольника всегда можно расположить так, чтобы друг напротив друга располагались вершины разного цвета. Резюме — хроматическое число графа = 3.

У треугольника хроматический индекс 3. Раскрасим оба треугольника одинаково - чтобы лежащие напротив друг друга рёбра были одинакового цвета. Рёбра 12, 43, 56 можно раскрасить теми же самыми тремя цветами, чтобы они не совпадали с цветами рёбер, сходящихся в соответствующей вершине треугольника. Резюме — хроматический индекс графа = 3.

@javavirys 12 / 12 / 4 Регистрация: 07.11.2013 Сообщений: 156
		1
	Хроматическое число и хроматический индекс графов 13.04.2014, 20:00. Показов 5393. Ответов 1 Метки нет (Все метки) Найдите хроматическое число и хроматический индекс графов: Вычислил степени всех вершин: deg1=3,deg2=3,deg3=3,deg4=3,deg5=3,deg6=3 А дальше что-то не пойму, с раскрасками Изображения 0

@AdmiralHood 477 / 280 / 90 Регистрация: 15.11.2013 Сообщений: 530
	14.04.2014, 13:33	2
	Сообщение было отмечено javavirys как решение Решение У треугольника хроматическое число 3. Ваш граф - это два треугольника, соответственные вершины которых соединены рёбрами. Два треугольника всегда можно расположить так, чтобы друг напротив друга располагались вершины разного цвета. Резюме — хроматическое число графа = 3. У треугольника хроматический индекс 3. Раскрасим оба треугольника одинаково - чтобы лежащие напротив друг друга рёбра были одинакового цвета. Рёбра 12, 43, 56 можно раскрасить теми же самыми тремя цветами, чтобы они не совпадали с цветами рёбер, сходящихся в соответствующей вершине треугольника. Резюме — хроматический индекс графа = 3. 1

Хроматическое число и хроматический индекс графов

Решение