✅ The verified answer to this question is available below. Our community-reviewed solutions help you understand the material better.
Vaatleme suundade määramise teoreemi.
Teoreem. Kui sidusas suunamata graafis ei leidu ühtegi silda, siis saab graafi servadele määrata suunad nii, et tekkinud suunatud graaf on tugevalt sidus. Tõestuse algusosas leiame graafis G tsükli C ja orienteerime selle tsükli servad ühes suunas. Tõestuse lõpuosa. On kaks võimalust. 1) Kõik G tipud kuuluvad tsüklisse C. Võib juhtuda, et mõni G serv ei kuulu tsüklisse C. Siis võime talle määrata suvalise suuna. Saadud suunatud graaf on tugevalt sidus. 2) Mõni G tipp ei kuulu tsüklisse C. Siis leidub sidususe tõttu G serv, mis ühendab tsükli C mingit tippu v mingi tipuga u väljaspool tsüklit. Ka serv vu peab sisalduma mingis tsüklis ja seega peab lisaks ahelale v, u leiduma veel üks ahel tippude u ja v vahel. Liigume seda pikemat ahelat pidi tipust u tippu v ja olgu w esimene ahela tipp, mis kuulub tsüklisse C. Määrame ahela v, u, . . ., w servadele suuna tipu v poolt tipu w poole. Omavahel kaartega ühendatud tippude hulgas pääseb nüüd endiselt igast tipust igasse teise. Nii jätkame, kuni kõik G tipud on ühendatud mingisse suunatud tsüklisse. |
Tõestuse lõpuosa punktis 2) kirjeldatakse sammu, kus tsükliga C ühendatakse teatav ahel. Märgi kõik tõesed laused.