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

@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.

Новые блоги и статьи Все статьи Все блоги /
Сайт компании Red-Star-Soft переехал на новый хостинг! Etyuhibosecyu 06.03.2025 Как и советовал Rius, я покинул хостинг от "Ru-Center" и перенес сайт red-star-soft. com на хостинг с более позитивными отзывами (спойлер: найти его было далеко не просто) (чтобы прочитать текст,. . .	Альтернативная сериализация в Java: сравнение Kryo, Protobuf и Avro Jamaican 06.03.2025 Сериализация — один из краеугольных процессов в Java-разработке. Превращение объектов в поток байтов для хранения или передачи по сети с последующим восстановлением звучит просто, но реализация этого. . .	Битва Java-кешей: Сравниваем Ehcache, Caffeine и Hazelcast Jamaican 06.03.2025 Производительность — вечный Святой Грааль для Java-разработчиков. Мы оптимизируем алгоритмы, настраиваем JVM, распараллеливаем процессы, но неизменно приходим к одному и тому же средству ускорения —. . .	Параметры подтверждения сообщения Kafka Jamaican 06.03.2025 Среди распределённых систем и высоконагруженных приложений Apache Kafka занимает особое место. Эта платформа потоковой обработки данных давно стала стандартом де-факто для организаций, которым. . .	Оптимизация времени запуска Spring Boot Jamaican 06.03.2025 Вы когда-нибудь сидели, барабаня пальцами по столу, пока ваше Spring Boot приложение медленно поднимается? Этот момент, когда вы успеваете сходить за кофе, пообщаться с коллегами и вернуться, а. . .
Деплой Kubernetes в Java: масштабирование Spring Boot приложений Jamaican 06.03.2025 Когда ваше Spring Boot приложение внезапно получает всплеск трафика или требует плавного обновления без простоя — традиционные методы деплоя часто пасуют. Именно здесь на сцену выходит Kubernetes —. . .	Бессерверные приложения Java: сравнение AWS Lambda и Azure Functions Jamaican 06.03.2025 Что такое "бессерверные приложения" и почему они так привлекательны? Вопреки названию, серверы никуда не исчезли — просто теперь управление инфраструктурой перекладывается на плечи облачного. . .	Безопасность микросервисов с OAuth2 и OpenID Connect Jamaican 06.03.2025 С ростом популярности микросервисов растут и проблемы, связанные с их безопасностью. В отличие от монолитных приложений, где безопасность можно было обеспечить централизованно, микросервисная. . .	Структурное логирование в Spring Boot Jamaican 06.03.2025 Представьте, что вы управляете сотней микросервисов в продакшн-среде. Внезапно один из сервисов начинает давать сбои, и вам нужно срочно выяснить причину. Вы открываете логи и видите бесконечные. . .	Предотвращение XSS, CSRF и SQL-инъекций в JavaScript bytestream 05.03.2025 В эпоху цифровизации безопасность веб-приложений становится не просто рекомендацией, а жизненной необходимостью. Если вы разрабатываете приложения на JavaScript, вам наверняка знакома эта. . .

@javavirys 12 / 12 / 4 Регистрация: 07.11.2013 Сообщений: 156
		1
	Хроматическое число и хроматический индекс графов 13.04.2014, 20:00. Показов 5604. Ответов 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

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

Решение