Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. • 17.108. Докажите, что ни один из графов, изображенных на рис
|
|
• 17.108. Докажите, что ни один из графов, изображенных на рис. 17.24, не может быть планарным.
17.109. Разработайте АТД графа для клиентской программы, которая выясняет, содержит ли заданный граф хотя бы один из графов, показанных на рис. 17.24. Для этой цели воспользуйтесь алгоритмом решения " в лоб", в котором вы проверяете все возможные подмножества из пяти вершин для клики и все возможные подмножества из шести вершин для полного двудольного графа. Примечание: Этой проверки не достаточно, чтобы показать, что граф планарный, поскольку она игнорирует условие, со-
Часть 5. Алгоритмы на графах
гласно которому удаление вершин степени 2 в некоторых подграфах может дать один из двух запрещенных подграфов.
17.110. Начертите графы
3-7 1-4 7-8 0-5 5-2 3-0 2-9 0-6 4-9 2-6 6-4 1-5 8-2 9-0 8-3 4-5 2-3 1-6 3-5 7-6,
в котором нет пересекающихся ребер, либо докажите, что такой чертеж невозможен.
17.111. Найдите такой способ выбрать 3 цвета вершинам графа
3-7 1-4 7-8 0-5 5-2 3-0 2-9 0-6 4-9 2-6 6-4 1-5 8-2 9-0 8-3 4-5 2-3 1-6 3-5 7-6,
чтобы ни одно ребро не соединяло вершины одного и того же цвета, либо покажите, что это сделать невозможно.
17.112. Решите задачу независимого множества для графа
3-7 1-4 7-8 0-5 5-2 3-0 2-9 0-6 4-9 2-6 6-4 1-5 8-2 9-0 8-3 4-5 2-3 1-6 3-5 7-6.
17.113. Каков размер максимальной клики в графе Де-Бруйна порядка л?
