Студопедия

КАТЕГОРИИ:

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



СД типа граф.




Читайте также:
  1. ИЗЯ, ТЕЛЕФОН, ТЕЛЕГРАФ...

Граф – двойка G = (X, U), где X – множество элементов (вершин, узлов), а U представляет собой бинарное отношение на множестве X (U Í X´X). Если |X| = n (конечно), то граф является конечным. Элементы U называют либо дугами, либо ребрами.

       
 
   
X = {X1, X2, X3, X4} X´X = {(X1,X1), …,(X4,X4)} U = {(X1,X2), (X1,X3), (X2,X3), (X2,X4)} Þ U Í X´X = X2
 

 

 


Если (Xi, Xj) – упорядоченная пара, то такой граф называется ориентированным (орграфом), а элементы U называются дугами. Если (Xi, Xj) = (Xj, Xi), то граф – неориентированный (неорграф), а элементы U называются ребрами.

F: U ® R – если задана такая функция, то граф является взвешенным, где R – множество вещественных чисел, т.е. отображение дуги на число.

Вообще: Æ U Í X × X.

Компонентами орграфа являются: дуга, путь, контур. Путь – такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом последующей. Контур – конечный путь, у которого начальная вершина совпадает с конечной. Контур единичной длины называют петлей.

X3
X2
Компонентами неорграфа являются, соответственно: ребро, цепь, цикл. Цепь – непрерывная последовательность ребер между парой вершин неориентированного графа. Неориентированный граф называют связным, если любые две его вершины можно соединить цепью. Если же граф – несвязный, то его можно разбить на подграфы. Например:

           
   
 
     
G = G1 U G2
 

 

 


Слабая связность – орграф заменяется неориентированным графом, который в свою очередь является связным. Односторонняя связность – это такая связность, когда между двумя вершинами существует путь в одну или в другую сторону. Сильная связность – это связность, когда между любыми двумя вершинами существует путь в одну и в другую сторону.


Дата добавления: 2015-04-18; просмотров: 6; Нарушение авторских прав





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