Взвешенный граф. Графы-деревья

Взвешенный граф

Взвешенным графом называется граф, вершинам и (или) рёбрам которого присвоены "весы" - обычно некоторые числа. Пример взвешенного графа - транспортная сеть, в которой рёбрам присвоены весы, означающие стоимость перевозки груза по ребру и пропускные способности дуг. Пример взвешенного графа на рисунке ниже.

Графы-деревья

Деревом называется связный граф без циклов (рисунок ниже). Любые две вершины дерева соединены лишь одним маршрутом.

Число q рёбер графа находится из соотношения

q = n - 1,

где n - число вершин дерева.

Приведённое соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро, то будет создан цикл, а если уберём одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.

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

⇐ Предыдущая 1 2 34