![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Типы графов
Граф G = (V, E) называют полным, если для любой пары вершин vi и vj в V существует ребро (vi, vj) в неориентированном графе Граф G = (V, E) называется симметрическим, если в множестве дуг E для любой дуги (vi, vj) существует также противоположно ориентированная дуга (vj, vi) (рис. 5, б). Антисимметрическим называется такой граф, для которого справедливо следующее условие: если дуга (vi, vj)∈ A, то во множестве A нет противоположно ориентированной дуги, т. е. (vj, vi)∉ A (рис. 5, в). Очевидно, что в антисимметрическом графе нет петель. В качестве примера можно рассмотреть граф, являющийся моделью некоторой группы людей: вершины графа интерпретируют людей, а дуги – их взаимоотношения. Так, если в графе дуга, нарисованная от вершины vi к вершине vj, означает, что vi является другом или родственником vj, тогда данный граф должен быть симметрическим. Если дуга, направленная от vi к vj, означает, что вершина vj подчинена вершине vi, то такой граф должен быть антисимметрическим. Комбинируя определения полного и симметрического графов и полного и антисимметрического графов, получили следующие определения: · граф G =(V, E), в котором любая пара вершин (vi, vj) соединена двунаправленными дугами, называется полным симметрическим (рис. 5, г); · граф G =(V, E), имеющий для каждой пары вершин (vi, vj) только одну дугу, называется полным антисимметрическим или турниром. Рисунок 5 Связный граф, не имеющий циклов, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью, называется деревом (рис 6). Граф типа “дерево”: а – неориентированное дерево, б – ориентированное дерево.
Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной (например, вершины v1), равна 1, а полустепень захода вершины v1 (называют корнем этого дерева) равна 0 (рис 6, б).
Рисунок 6 Граф G =(V, E), который может быть изображен на плоскости или сфере без пересечений называется планарным (рис 7). Рисунок 7 На рис. 8 показаны непланарные графы. Эти два графа играют важную роль в теории планарных графов и известны как графы Куратовского. Рисунок 8 Неориентированный граф G = (V, E)называют двудольным, если множество его вершин V может быть разбито на такие два подмножества Vа и Vb, что каждое ребро имеет один конец в Vа, а другой в Vb (рис. 9, а). Ориентированный граф G называется двудольным, если его неориентированный двойник – двудольный граф (рис. 9, б, в). Двудольный граф G=(Vа∪ Vb, E) называют полным, если для любых двух вершин vi∈ Vа и vj ∈ Vb существует ребро (vi, vj) в G=(V, E) (рис. 9, г). Рисунок 9
|