Основная образовательная программа cb. 5005. 2016 Прикладная математика, фундаментальная информатика и программирование
 Скачать 0.51 Mb.
|
Определение 1.1.Маршрут — последовательность узлов  , возможно повторяющихся, графа  , где каждой паре  ставится в соответствие ребро  для всех  .Определенный подобным образом маршрут проходит по ребрам  и узлам  . Маршрут замкнут, если  .Ребра, по которым проходит маршрут, не обязательно различны. На рисунке 1.1 изображен маршрут, состоящий из 5 узлов и 5 ребер.  Рисунок 1.1 - Маршрут 1-2-3-4-5-1 Определение 1.2.Путем называется маршрут не имеющий повторяющихся ребер. Путь так же является подграфом графа , и состоит из компонент пути - узлов и ребер. Узел  называется началом, а узел  — концом пути. Путь называется простым, когда все его узлы  попарно различны. Длина пути — это общее количество его ребер. На рисунке 1.2 изображен простой путь, длина которого равна трем.  Рисунок 1.2 - Простой путь 1-3-4-2 Определение 1.3.Циклом называется последовательность узлов и различных ребер  графа , где каждой паре ставится в соответствие ребро для всех  , при  .Определенный подобным образом цикл проходит по ребрам и узлам .Аналогично пути цикл является подграфом графа , и из узлов и рёбер, его составляющих.На рисунке 1.3 изображен цикл, состоящий из 5 узлов и 6 ребер.  Рисунок 1.3 - Цикл 1-2-3-1-4-5-1 Цикл называется простым, когда все его узлы попарно различны.Длина цикла — это общее количество его ребер. На рисунке 1.4 изображен цикл, длина которого равна 5.  Рисунок 1.4 - Простой цикл 1-2-3-5-4-1 Определение 1.4.Если  — простой цикл, и  ,  — два его несмежных узла. При том  , тогда ребро  называется хордой цикла .На рисунке 1.5 изображен простой цикл, содержащий хорду.  Рисунок 1.5 - Простой цикл 1-2-3-4-5-6-1, черным выделена содержащаяся в нем хорда 2-6 |