Сечения

20 Кесінділер, кесінділер рангі

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

Число этих ребер определяет ранг сечения

Если граф имеет хотя бы одну пару вершин x_i и x_j, соединенных m ребрами (или дугами) одного направления, он называется мультиграфом.

Если ребро графа G=(X, U) соединяет вершины , т.е. , то говорят, что ребро инцидентно вершинам . Справедливо и обратное – вершины инцидентны ребру.

Если две вершины соединены ребром, то они называются смежными.

Если два ребра инцидентны одной вершине, то они называются смежными. Следовательно, отношения инцидентности и смежности имеют место как на множестве вершин, так и на множестве дуг.

Число ребер, инцидентных вершине , называется локальной степенью этой вершины.

Цикломатическим числом графа называется наименьшее число ребер, которое необходимо удалить из графа G=(X, U), чтобы он стал деревом (т. е. ациклическим). Цикломатическое число v=|U|-|X|+1

где |X| - число вершин графа, |X|=n;

|U| - число дуг графа, |U|=m,

v=m-n+1

Сечением s сети назовем минимальную совокупность ребер, которые надо изъять из сети, чтобы нарушилось ее связность. Сечением s_ST по отношению к узлам S и Т будем называть такие сечения, при которых названные узлы будут находиться в разных подсетях. Рангом сечения называется число входящих в него ребер.

Дата добавления: 2015-07-17