Студопедия

КАТЕГОРИИ:

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



Пример 20. Проверить, будет ли данный граф гамильтоновым.




Читайте также:
  1. II. Средства, применяемые при лечении заболеваний, вызванных условно-патогенными грибами (например, при кандидамикозе)
  2. III. Примерная структура фронтального занятия.
  3. TG Дополнительные признаки, например, Case Report - описание случая
  4. V. ПРИМЕРЫ ИССЛЕДОВАНИЯ ФУНКЦИЙ
  5. V. Сравнительный анализ НДС расчетных схем и пример расчета.
  6. Активный транспорт ионов. Механизм активного транспорта ионов на примере натрий-калиевого насоса
  7. Алгоритмы разгона и торможения. Сравнительная оценка алгоритмов. Примеры.
  8. Антиконцепции. Определение и виды. Примеры концепции о «будущем».
  9. Аутсорфинг: понятие, примеры.
  10. Аэробное и анаэробно-аэробное энергообеспечение мышечной деятельности, средства и методы повышения их мощности и емкости на примере избранного вида спорта.

Проверить, будет ли данный граф гамильтоновым.

 


Рис.12

 

Решение.

Данный граф является гамильтоновым, так как он имеет гамильтоновы циклы и .

· Ориентированные графы

Ребро графа G(X,T) называется ориентированным, или дугой, если одну вершину считают началом, а вторую концом ребра.

На рисунке дугу изображают стрелкой. Дугу с началом в вершине и концом в вершине записывают ( ).

Граф, все ребра которого ориентированы, называется ориентированным графом.

Вершина называется источником, если из неё только выходят дуги; вершина называется стоком, если в неё только входят дуги .

Например.Рассмотрим ориентированный граф

 

 

 


Рис.13

 

Вершина является источником, вершина является стоком.

Последовательность дуг ( ), ( )… ( ), в которой конец предыдущей дуги совпадает с началом следующей, называется маршрутом от .

Маршрут, в котором первая и последняя вершины совпадают, называется замкнутым.


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







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