nimetatakse sidusaks o kui graaf ei ole sidus, siis koosneb ta eraldiseisvatest sidusatest osadest, mida nimetatakse sidusateks komponentideks Graafi serva, mille eemaldamisel graafi sidusate komponentide arv kasvab, nimetatakse sillaks Graafi tippu, mille eemaldamisel graafi sidusate komponentide arv kasvab, nimetatakse eraldavaks tipuks Tarvilik ja piisav tingimus silla jaoks: graafi serv on sild parajasti siis, kui ta ei kuulu ühessegi tsüklisse Sidususteoreem: kui n-tipulisel graafil on m serva ja k sidusat (n-k )(n-k +1) komponenti, siis kehtivad võrratused n-k <= m <= 2 o Järeldus: kui n-tipulisel graafil on vähem kui n-1 serva, siis see graaf on mittesidus (n-k )(n-k +1) o Järeldus: kui n-tipulisel graafil on rohkem kui 2
omaette on sidus graaf. Neid osi nimetatakse sidusateks komponentideks. c. Graafi serva nimetatakse sillaks, kui tema eemaldamisel graafi sidusate komponentide arv kasvab. d. Graafi tippu nimetatakse eraldavaks tipuks, kui tema eeldamisel koos kõigi temaga intsidentsete servadega graafi sidusate komponentide arv kasvab. e. Tarvilik ja piisav tingimus silla jaoks, https://moodle.ut.ee/mod/url/view.php? id=107318 lk 54. 37) a. Sidususteoreem. Kui n-tipulisel graafil on m serva ja k sidusat komponenti, siis kehtivad võrratused b. Tõestus. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 54 55 38) a. Tsüklit, mis läbib graafi kõik servad täpselt üks kord, nimetatakse Euleri tsükliks. b. Graafi, kus leidub Euleri tsükkel, nimetatakse Euleri graafiks. c. Nt, postiljoni marsruudi valimine, et ühtegi tänavat mitu korda ei läbiks. d. Euleri graafi leidumise kriteerium
Tarvilik ja piisav tingimus silla jaoks o Teoreem. Graafi serv on sild parajasti siis, kui ta ei kuulu ühessegi selle graafi lihttsüklisse. o Tarvilikkus. Sild ei saa kuuluda lihttsüklisse, sest tsüklist serva eemaldamisega ei saa katkeda ühendus serva otstippude vahel. o Piisavus. Kui serv ei kuulu ühessegi lihttsüklisse, siis peab tema eemaldamisel ühendus serva otstippude vahel katkema. 39. Sidususteoreem. [2] o Teoreem. Kui n-tipulisel graafil on m serva ja k sidusat komponenti, siis kehtivad võrratused o Tõestus. 1) induktsiooniga m järgi, 2) mitu serva saab olla k komponendi ja n tipu korral? o Järeldus. Kui n-tipulisel graafil on vähem kui n-1 serva, siis see graaf on mittesidus. o Järeldus. Kui n-tipulisel graafil on rohkem kui (n-1)(n-2)/2 serva, siis see graaf on sidus. 35 40
annaabi.ee 
