Matek érettségi kérdés?

Most van x város, mondjuk 6.

Azt mondod, hogy minden városból minden városba megy egy út, ami csak egyirányú?

Mert akkor minden városnak hat útja van.

Küldd már el a feladatot mert ez így számomra értelmetlen.

Rajzold fel gráffal a városokat és az utakat. Szerintem akkor jutsz el minden városba, ha ebben az irányított gráfban kör van.

Tehát valahogy így:

[] --> [] --> [] --> [] --> [] -|

^^-------------------------------

Szükseéges és elégséges feltétel, hogy nincs olyan vágás a gráfban, amit csak az egyik irányból kereszteznek az élek.

Ha van ilyen vágás, akkor triviális, hogy van két pont, melyek között elgfeljebb az egyik irányban van út (gráfeélméletileg értelemzett út, nem a városok közötti "út", amik a gráf élei).

Amennyiben nincs ilyen vágás, akkor indukcióval biznyítjuk az erős összefüggőséget. n=3-ra jók vagyunk, hiszen ez ekkor egy kör. n=1 és n=2 eset triviális.

Tegyük föl, hogy k csúcsig igaz az állításunk. Az indukciós lépés indirekt lesz: tegyük föl, hogy nem lehet eljutni x csúcsból y-ba az irányított, k+1 csúcsú gráfban. Ekkor válasszunk egy tetszőleges P1, P2 vágást, amiben x P1-be kerül, y pedig P2-be. A feltevésünk szerint ez a vágás nem egyirányú, tehát van él, ami P1-ből P2-be vezet. Legyen ez az él az ab él. Azt is tudjuk, hogy P1 és P2 is legfeljebb k csúcsot tartalmaz. Tehát az indukciós feltevés szeritn P1-ben van x-a út, P2-ben pedig b-y út. Tehát az teljes gráfban van x-y út, ami ellentmondás, azaz az indukciós lépés igaz.