Граф со взвешенными дугами

Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую называют весовой функцией.

Тем самым в взвешенном графе G каждой дуги xA поставлено в соответствие некоторое действительное число l(x). Значение l(x) называются длиной дуги x.

Для любого пути P_i взвешенного графа G обозначающим через l(P_i) сумму длин входящих в P_i дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину l(P_i) называют длиной путиP_i в взвешенном графе G.

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

Если допускаются петли, противоположные и кратные ребра, получаем псевдограф.

Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G.

Дуги 8,9 - называются параллельными (кратными). Дуги 5,6 - называются противоположными. Вершина k - называется изолированной.

Определение. Полным графом называется граф с n вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого любые две вершины соединены дугой.

Определение. Полным двудольным графом называется граф с n+m вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого множество вершин разбито на два непересекающихся подмножества с n и m вершинами так, что любые две вершины различных подмножеств соединены дугой и никакие две вершины одного подмножества не соединены дугой.