Графы

Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром, называются смежными. Если две вершины, соединяемые ребром, совпадают, то такое ребро называется петлей Число рёбер, выходящих из вершины, называется степенью вершины. g f ce b a d

Если рёбра соединяют одну и ту же пару вершин, они называются кратными. Если ребро имеет направление, то оно называется дугой, а граф - ориентированным f ce g b a d

f ce b a d g a b c g f d e Для неориентированного графа порядок вершин неважен! {1,2,3,4} a: (1,2) b: (1,3) c: (1,3) d: (1,3) e: (1,3) f: (1,2) g: (1,3)

ce b a d ab 2acd 3bce 4de Пустой граф – нет рёбер, состоит из изолированных вершин Полный граф – неориентированный граф, в котором нет кратных рёбер и петель и любые две вершины соединены ребром.

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

Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в Б не больше 6»