Пытаетесь найти бесплатную помощь в интернете, но не удается?
Вас интересует какой-то вопрос или хотите проверить свое решение?
Мы сделали универсальный сервис, где математики помогут Вам.

Фундаментальные циклы и фундаментальные разрезы графов
Поступил вопрос 19 Декабря 2017 по предмету

Для неорграфа С найти: а) один из остовов Т; б) все фундаментальные циклы относительно остова Т: в) матрицу фундаментальных циклов относительно остова Т: г) все фундаментальные разрезы относительно остова Т: д) матрицу фундаментальных разрезов относительно остова Т.

Прикрепленные файлы:

Поступил ответ 19 Декабря 2017 от Викиматика

а) Найдем один из остовов графа $G$. Предварительно введем обозначения для ребер графа $G$.

Согласно определению, $T=\left(V',\ E'\right)$ — остов графа $G\left(V,\ E\right)$, если $V'=V$ и $T$ является лесом, который образует дерево на каждой связной компоненте графа $G$. Поскольку граф $G$ содержит 8 вершин ($n=8$), 13 ребер ($m=13$) и 1 связную компоненту ($k=1$), то всякий остов графа $G$ имеет 7 ветвей ($n-k\ =7$) и 6 хорд ($m-\left(n-k\right)=6$). В качестве остова $T$ выберем следующую часть графа $G$:

$T=\left(V',\ E'\right)$, где $V'=V$, $E'=\left\{u_1,\ u_2,\ u_3,\ u_4,\ u_5,\ u_9,\ u_{11}\right\}$.

б) Найдем фундаментальные циклы графа $G$ относительно остова $T$. Согласно определению, фундаментальным циклом графа $G$ относительно остова $T$ и хорды $u$ называется цикл $C$ графа $G$, состоящий из хорды $u$ и тех ветвей остова $T$, которые соединяют концы хорды $u$ простой цепью. Поэтому граф содержит столько фундаментальных циклов, сколько хорд имеет его остов. Таким образом, граф $G$ имеет 6 фундаментальных цикла:

$$C_1=\left\{u_7,u_2,u_1\right\},\ C_2=\left\{u_8,u_3,u_2,u_1\right\},\ C_3=\left\{u_{10},\ u_3,u_9\right\},\ C_4=\left\{u_{12},\ u_5,\ u_4\right\},\ C_5=\left\{u_{13},\ u_4,\ u_{11}\right\},\ C_6=\left\{u_6,\ u_{11},\ u_3,\ u_9\right\}.$$ 

в) Найдем матрицу фундаментальных циклов графа $G$ относительно остова $T$. Согласно определению, матрицей фундаментальных циклов графа $G$ относительно остова $T$ называется матрица размера $\left(m-\left(n-k\right)\right)\times m$ вида:

Следовательно, матрица фундаментальных циклов графа $G$ относительно остова $T$ имеет вид:

г) Найдем фундаментальные разрезы графа $G$ относительно остова $T$. Согласно определению, фундаментальным разрезом графа $G$ относительно остова $T$ и ветви $v$ называется разрез $L$ графа $G$, состоящий из ветви $v$, которая является простым разрезом остова $T$ по некоторому разбиению $V_1,V_2$, и всех хорд остова $T$, которые соединяют вершины из $V_1$ с вершинами из $V_2$. Поэтому граф содержит столько фундаментальных разрезов, сколько ветвей имеет его остов. Таким образом, граф $G$ имеет 7 фундаментальных разрезов:

$$L_1=\left\{u_1,u_7,\ u_8\right\},\ L_2=\left\{u_2,u_7,u_8\right\},\ L_3=\left\{u_3,u_8,u_{10},\ u_6\right\},\ L_4=\left\{u_4,u_{12},\ u_{13}\right\},\ L_5=\left\{u_5,\ u_{12}\right\},\ L_6=\left\{u_9,\ u_6,\ u_{10}\right\},\ L_7=\left\{u_{11},\ u_6,\ u_{13}\right\}.$$ 

д) Найдем матрицу фундаментальных разрезов графа $G$ относительно остова $T$. Согласно определению, матрицей фундаментальных разрезов графа $G$ относительно остова $T$ называется матрица $N$ размера $\left(n-k\right)\times m$ вида:

Следовательно, матрица фундаментальных разрезов графа $G$ относительно остова $T$ имеет вид:

×