Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 4.4. Размерность подпространств циклов и разрезовВ этом разделе мы покажем, что размерность подпространств циклов и размерность разрезов соответственно равны цикломатическому числу и рангу графа. Для этого докажем, что множество базисных циклов и множество базисных разрезающих множеств по отношению к некоторому остову связного графа являются соответственно базисами для подпространства циклов и подпространства разрезов графа. Пусть Т — остов связного графа G на По определению каждый базисный цикл включает в себя только одну хорду, не присутствующую ни в одном другом базисном цикле. Таким образом, никакой базисный цикл нельзя представить в виде кольцевой суммы других базисных циклов. Следовательно, базисные циклы Чтобы доказать, что С — кольцевая сумма базисных циклов Теорема 4.6. Пусть G — связный граф на 1. Базисные циклы по отношению к остову графа G образуют базис подпространства циклов графа, и, следовательно, размерность подпространства циклов графа G равна 2. Базисные разрезающие множества по отношению к остову графа G образуют базис подпространства разрезов графа G, и, следовательно, размерность подпространства разрезов графа равна
Рис. 4.3. Теперь нетрудно видеть, что в случае несвязного графа G множества всех базисных циклов по отношению к хордам леса графа G и разрезающих множеств по отношению к ветвям леса графа G являются базисами подпространств циклов и разрезов графа G соответственно. Таким образом, получаем следствие из предыдущей теоремы: Следствие 4.6.1. Если граф на 2. Размерность подпространства разрезов графа G равна В качестве примера рассмотрим граф G, изображенный на рис. 4.3. Ребра
Рассмотрим сначала подграф С, состоящий из ребер Поскольку хорды
Теперь рассмотрим разрез В предыдущих рассуждениях мы показали, что, имея остов, можно построить базисы подпространств циклов и разрезов графа. Построенные таким образом базисы обычно используются при изучении электрических цепей.
|
1 |
Оглавление
|