Фундаментальні цикли і розрізи - студопедія

Нехай Т - остов графа і К - відповідний йому ко-ліс.

Якщо додати до Т будь-яку хорду h ÎК. то отримаємо єдиний цикл, який називається фундаментальним циклом щодо хорди h. Зрозуміло, що все цикли, одержувані таким способом, тобто шляхом додавання до Т різних хорд з К. попарно різні і їх число дорівнює числу хорд в К. і одно g (G). Безліч всіх фундаментальних циклів щодо хорд До називається фундаментальною системою циклів щодо остова Т.

На малюнку 30 (а) і (б) зображено граф і його остов, а на малюнку 30 (в) - фундаментальна система циклів щодо цього остова.

Якщо видалити з Т будь-яку гілку b. то одна з компонент Т розіб'ється на дві нові компоненти, кожна з яких є деревом. Позначимо безлічі вершин нових компонент V1 і V2. Зауважимо тепер, що хорди з К. з'єднують вершини з V1 і V2. в сукупності з гілкою b утворюють розріз графа G. Цей розріз називається фундаментальним розрізом щодо гілки b остова Т. Безліч всіх розрізів, отриманих таким способом, тобто видаленням окремо кожної гілки з Т. називається фундаментальною системою розрізів щодо остова Т. Очевидно, що всі розрізи в цій множині попарно різні і їх число збігається з числом гілок в Т і одно (в # 8209; k).

На малюнку 31 зображені фундаментальні розрізи графа, зображеного на рис.30 (а), щодо його остова на рис.30 (б). Мал. 31 (а) - фундаментальний розріз щодо гілки (1,5); Мал. 31 (б) - ф.р. щодо гілки (2,5); Мал. 31 (в) - ф.р. щодо гілки (3,5) і рис. 31 (г) - ф.р. щодо гілки (4,5).

Важливою особливістю фундаментальних циклів (розрізів) є те, що будь-який цикл (розріз) в графі можна представити у вигляді кільцевої суми деяких фундаментальних циклів (розрізів). У цьому сенсі вони утворюють базис підпростору всіх циклів (розрізів) графа G.