Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2020-10-20 | 723 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!