Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Задание 3.




Определить, является ли данный граф:

- планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);

- двудольным графом (обосновать ответ и, если необходимо, то достроить до двудольного графа);

- деревом (обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева);

- псевдографом или мультиграфом, или простым графом (обосновать ответ и выполнить необходимые преобразования).

Решение:

Данный граф является плоским, поскольку все его связи пересекаются только в вершинах. Преобразуем данный граф в планарный граф:

Х2 V4 Х3

       
 
   
 

 


V2 V3 V5 V6

 

 
 


X1V1 X4V7 X5

Данный граф не является двудольным, поскольку содержит циклы нечетной длины (например, х4-х3-х5-х4), и поэтому множество его вершин нельзя разделить на две части.

Для того, чтобы преобразовать граф в двудольный, необходимо, например, заменить ребро V3 на два ребра V3-1 и V3-2 с добавлением вершины Х2_4 и ребро V6 – на V6-1 и V6-2 с добавлением вершины Х3_5. В результате данного преобразования исходного графа все циклы в графе будут иметь четную длину, тогда множество вершин можно следующим образом разделить на две доли (1 и 2 – это номер доли):

 
 


2 1 2

Х3_5

 
 


1

Х2_4

 
 


1 2 1

 

Данный граф не является деревом, поскольку он содержит циклы. Приведем пример остова данного графа:

Х2 Х3

V4

           
   
     
 
 
 

 


V2 V3 V6

 


Поделиться:

Дата добавления: 2015-09-13; просмотров: 62; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты