Diskreetse matemaatika elemendid
Sild, eraldav tipp
o DEF: Serva, mille eemaldamisel graafi sidusate komponentide arv kasvab, nimetatakse
sillaks.
o Analoogilise omadusega tippu nimetatakse eraldavaks tipuks.
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.
annaabi.ee 
