Crowdly
Add to Chrome
Diskreetne matemaatika (LTMS.00.066)
Looking for Diskreetne matemaatika (LTMS.00.066) test answers and solutions? Browse our comprehensive collection of verified answers for Diskreetne matemaatika (LTMS.00.066) at moodle.ut.ee.
Get instant access to accurate answers and detailed explanations for your course questions. Our community-driven platform helps students succeed!
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.
Kuidas võib muutuda suunatud graafi tugevalt sidusate komponentide arv, kui graafist üks kaar kustutada?
Loengukonspektis tõestatakse, et suunatud tsükleid ja silmuseid mittesisaldavas graafis leidub sisend ja väljund.
Teoreem. Kui suunatud graafis pole suunatud tsükleid ja silmuseid, siis leidub graafil vähemalt üks sisend ja vähemalt üks väljund. Tõestus. |
Määra iga järgneva lause puhul, kas lause on selle teoreemi sõnastuses eeldus või väide või pole kumbki.
Vaatleme suunatud graafide tipuastmete teoreemi tõestust.
Teoreem. Igas suunatud graafis on tippude sisendastmete summa võrdne tippude väljundastmete summaga: Σv∈V d−(v) = Σv∈V d+(v). Tõestus. Tippude sisendastmete summa on võrdne graafi kaarte arvuga, sest selle summa leidmisel arvestame iga kaart ühe korra. Samamoodi on väljundastmete summa võrdne kaarte arvuga. Järelikult on need summad võrdsed. |
Milline lause võtab selle tõestuse kõige paremini kokku?
Ülesanne. Tõesta järeldumine ∀x(F(x)∨G) ⊨ ∀xF(x)∨G.
Tõestus. Valime vabalt interpretatsiooni α ja vabade muutujate väärtused. Eeldame, et ∀x(F(x)∨G) = 1. Siis iga elemendi m ∈ Mα puhul F(m)∨G = 1. On kaks võimalust: G = 1 või G = 0.
| 1) | Eeldame, et G = 1. Siis ∀xF(x)∨G = 1. | |
| 2) | Eeldame, et G = 0. Siis iga elemendi m ∈ Mα puhul F(m) = F(m)∨G = 1. Järelikult ∀xF(x) = 1. Seega ∀xF(x)∨G = 1. |
Mis lause sobiks järgmiseks?
Ülesanne. Tõesta järeldumine ∀x(F(x)∨G) ⊨ ∀xF(x)∨G.
Tõestus. Valime vabalt interpretatsiooni α ja vabade muutujate väärtused. Eeldame, et ∀x(F(x)∨G) = 1. Siis iga elemendi m ∈ Mα puhul F(m)∨G = 1. On kaks võimalust: G = 1 või G = 0.
| 1) | Eeldame, et G = 1. Siis ∀xF(x)∨G = 1. | |
| 2) | Eeldame, et G = 0. Siis iga elemendi m ∈ Mα puhul F(m) = F(m)∨G = 1. Järelikult ∀xF(x) = 1. |
Mis lause sobiks järgmiseks?
Ülesanne. Tõesta järeldumine ∀x(F(x)∨G) ⊨ ∀xF(x)∨G.
Tõestus. Valime vabalt interpretatsiooni α ja vabade muutujate väärtused. Eeldame, et ∀x(F(x)∨G) = 1. Siis iga elemendi m ∈ Mα puhul F(m)∨G = 1. On kaks võimalust: G = 1 või G = 0.
| 1) | Eeldame, et G = 1. Siis ∀xF(x)∨G = 1. | |
| 2) | Eeldame, et G = 0. Siis iga elemendi m ∈ Mα puhul F(m) = F(m)∨G = 1. |
Mis lause sobiks järgmiseks?