КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пример 20. Проверить, будет ли данный граф гамильтоновым.
Проверить, будет ли данный граф гамильтоновым.
|
|
|
|
|
|
|
Рис.12
Решение.
Данный граф является гамильтоновым, так как он имеет гамильтоновы циклы 
и 
.
· Ориентированные графы
Ребро графа G(X,T) называется ориентированным, или дугой, если одну вершину считают началом, а вторую концом ребра.
На рисунке дугу изображают стрелкой. Дугу с началом в вершине 
и концом в вершине 
записывают ( 
).
Граф, все ребра которого ориентированы, называется ориентированным графом.
Вершина 
называется источником, если из неё только выходят дуги; вершина называется стоком, если в неё только входят дуги .
|
|
|
|
|
|
|
|
|
|
Рис.13
Вершина 
является источником, вершина 
является стоком.
Последовательность дуг ( 
), ( 
)… ( 
), в которой конец предыдущей дуги совпадает с началом следующей, называется маршрутом от 
.
Маршрут, в котором первая и последняя вершины совпадают, называется замкнутым.
Дата добавления: 2015-07-26; просмотров: 122; Мы поможем в написании вашей работы!; Нарушение авторских прав |