Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Упражнения

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

4.2. Множество инциденций — множество ребер, инцидентных вершине. Покажите, что любая из множеств инциденций связного графа на вершинах образуют базис подпространства разрезов графа.

4.3. Покажите, что если — ранг, — цикломатическое число графа G, то а) число различных базисов для подпространства разрезов графа G равно ; б) число различных базисов для подпространства циклов графа G равно

4.4. Для графа G, представленного на рис. 4.6, найдите

а) множество базисных векторов подпространства циклов, которые не являются базисными циклическими векторами по отношению к какому-либо остову графа

Рис. 4.5.

Рис. 4.6,

б) множество базисных векторов подпространства разрезов, которые не соответствуют ни множествам инциденций, ни базисным разрезающим множествам по отношению к какому-либо остову графа

4.5. а) Проверьте, являются ли подпространства циклов и разрезов графа G (рис. 4.6) ортогональными дополнениями векторного пространства графа G; б) представьте граф G кольцевой суммой двух подграфов, один из которых принадлежит подпространству циклов, а другой — подпространству разрезов.

4.6. Покажите, что каждое подмножество множества ребер дерева является разрезом дерева.

4.7. Покажите, что подграф графа имеет четное число ребер, если он принадлежит одновременно подпространствам как циклов, так и разрезов графа.

4.8. Подмножество ребер графа G называется независимым, если оно не содержит циклов. Докажите следующее:

а) каждое подмножество независимого множества является независимым;

б) если независимые множества, содержащие k и ребер соответственно, то существует такое ребро входящее только в множество У, что — независимое множество.

4.9. Выполните упражнение 4.8, заменив термин «цикл» термином «разрезающее множество».

<< Предыдущий параграф Следующий параграф >>
Оглавление