mõlemas ühendamata. c. Kahe graafi isomorfsuse ümberlükkamiseks piisab vähemalt ühe invariandi erinevuse väljatoomisest. 36) a. Graafi, milles iga kahe tipu korral leidub neid tippe ühendav ahel, nimetatakse sidusaks. Kokkuleppeliselt loetakse ka ühetipuline graaf sidusaks. b. Kui graaf ei ole sidus, siis jaguneb ta eraldiseisvateks osadeks, millest igaüks 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
serv ei kordu Lihttsükliks nimetatakse tsüklit, kus iga sisetipp esineb ainult ühe korra Teoreem lihtahela ja lihttsükli leidumisest: kui graafi iga tipu aste on vähemalt l2, siis leidub graafis lihtahel pikkusega l ja lihttsükkel pikkusega vähemalt l+1 Graafi, milles iga kahe tipu korral leidub neid tippe ühendav (liht)ahel, 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)
numbritega tippude vahel ja vastupidi, siis on need graafid isomorfsed. 38. Sidusus. Sidus komponent. Sild. Eraldav tipp. Tarvilik ja piisav tingimus silla jaoks. [2] Sidusus o DEF: Graafi, milles iga kahe tipu korral leidub neid tippe ühendav (liht)ahel, nimetatakse sidusaks. Sidusaks loetakse ka ühetipulist graafi. Sidus komponent o Kui graaf ei ole sidus, siis koosneb ta eraldiseisvatest sidusatest osadest, mida nimetatakse sidusateks komponentideks. 34 o DEF: Sidus komponent on graafi maksimaalne sidus alamgraaf. 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
¨ Uldsust kitsendamata v˜oib eeldada, et c < d. Moodustame arvuhulga D = { g ∈ A | [c; g] ⊂ B }. Hulk D on u¨lalt t˜okestatud arvuga d ∈ A ning seet˜ottu leidub ¨lemine raja h = sup D, mis samuti kuulub hulka A, h ∈ tal u A. Arvu h igas u ¨mbruses peab leiduma siis nii hulga B kui ka hulga C punkte, st h ∈ cl(B) ∩ cl(C) = B ∩ C. See on vastuolus eeldusega B ∩ C = ∅. J¨arelikult on hulk A sidus. Teoreem 8.40 Mittet¨ uhjadeks sidusateks hulkadeks ruumis R on parajasti l˜oigud, pooll˜oigud ja vahemikud (ka l˜ opmatud). T˜oestus. Teoreemis 8.5 n¨aidati, et l˜oigud, pooll˜oigud ja vahemikud on sidusad hulgad arvteljel. Siin tuleb n¨aidata, et iga mittet¨uhi sidus hulk A ruumis R avaldub kujul A = < d; c >. Olgu A mittet¨ uhi sidus hulk ruumis R. Fikseerime a ∈ A ja moodustame arvuhulga B = { b ∈ R | [a; b] ⊂ A; a ≤ b } ⊂ A.
annaabi.ee 
