Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Интересное:
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2020-10-20 | 722 |
5.00
из
|
Заказать работу |
|
|
0. Выберем некоторый простой цикл С графа G и уложим его на плоскости; положим G'=С.
1. Найдем грани графа G' и сегменты относительно G'. Если множество сегментов пусто, то перейдем к п. 7.
2. Для каждого сегмента S определим множество Г(S).
3. Если существует сегмент S, для которого Г(S)=Æ, то граф G непланарен. Конец. Иначе перейти к п. 4.
4. Если существует сегмент S, для которого имеется единственная допустимая грань Г, то перейти к п. 6. Иначе – к п. 5.
5. Для некоторого сегмента S (Г(S)>1) выбираем произвольную допустимую грань Г.
6. Поместить произвольную a–цепь L ÎS в грань Г; заменить G' на G'ÈL и перейти к п. 1.
7. Построена укладка G' графа G на плоскости. Конец.
Проиллюстрируем работу алгоритма на примерах.
Пример 1. Для графа G, изображенного на рис 3, построить его укладку на плоскости.
Решение. Уложим сначала цикл С =(1, 2, 3, 4, 1), который разбивает плоскостьна две грани Г1 в Г2. На рис. 4 изображены граф G'=С и сегменты S1, S2, S3 относительно G'с контактными вершинами, обведенными кружками. Таккак Г(Si)={Г1, Г2} (i=1, 2, 3), то любую a-цепь произвольного сегмента можно укладывать в любую допустимую для него грань. Поместим, например, a-цепь L = (2, 5, 4) в Г1. Возникает новый граф G' и его сегменты (рис. 5). При этом Г(S1) = {Г3}, Г(S2) = {Г1, Г2}, Г(S3) = {Г1, Г2, Г3}. Укладываем цепь L = (1, 5) в Г3 (рис. 6). Тогда Г(S1) = {Г1, Г2}, Г(S2) = {Г1, Г2}. Далее, уложим a-цепь L = (2, 6, 4) сегмента S1 в Г1 (рис. 7). В результате имеем Г(S1) = {Г5}, Г(S2) = {Г1, Г2, Г3}. Наконец, уложив ребро (6,3) в Г5, а ребро (2,4) - например, а Г1, получаем укладку графа G на плоскости (рис. 8).
Рис. 3.
Рис. 4.
Рис. 5.
Рис. 6.
Рис. 7.
Рис. 8.
Пример 2. Для графа К3,3, изображенного на рис.9, построить, если это возможно, его укладку на плоскости.
|
Решение: цикл G' и сегменты относительно этого цикла изображены на рис. 10. При этом Г(Si) = {Г1, Г2} (i=1,2,3). Помещает S1 в грань Г2. Тогда S2 необходимо поместить в грань Г1 (рис. 11). Поскольку Г(S1)=Æ, то К3,3 - непланарный граф.
Рис. 9.
Рис. 10.
Рис. 11.
Контрольные вопросы:
1. Плоские графы.
2. Планарные графы.
3. Решить задачи:
1. Для графа построить, если это возможно, его укладку на плоскости.
а)
б)
2. Для графа построить, если это возможно, его укладку на плоскости.
а) б)
в) г)
Практические занятия
1. Практическое занятие №14 «Метрические характеристики графов»
КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Вопросы к экзамену
ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ПОДГОТОВКИ К СДАЧЕ ЭКЗАМЕНА ПО ДИСЦИПЛИНЕ «ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА»
Теоретическая часть:
Раздел 1. Основные понятия комбинаторики
Тема 1.1. Основные понятия комбинаторики
1. Основные комбинаторные объекты. Размещения. Примеры
2. Основные комбинаторные объекты. Сочетания. Примеры
3. Основные комбинаторные объекты. Перестановки. Примеры.
4. Два основных принципа комбинаторики
Раздел 2. Основы теории вероятностей
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!