Iskola további matematikai kialakulását
Ábra által képzett véges ponthalmaz a síkban, és a szegmensek csatlakoztassa-nek néhány ilyen pontot nevezzük síkbeli gráf. vagy egyszerűen egy grafikon (ábra. 2.1, a). A pontok nevű csúcsot. és szegmenseket - egy él.
Ehelyett a szegmenseket gráf élei is megfontoljuk görbék egy síkban (ábra. 2.1b).
grafikonok példák közé földalatti áramkört, vasutak és az autópályák, kiállítások tervek, stb A grafikonok azt mutatják, különféle kapcsolatok az objektumok között.
Történelmileg, hogy gráfelmélet során keletkezett a rejtvények megoldása több mint kétszáz évvel ezelőtt.
Az egyik ilyen probléma puzzle volt a probléma a Königsberg híd, amely felkeltette a Leonhard Euler (1707-1783), hosszú ideig élt és dolgozott Oroszországban (1727-1741 és 1766-től haláláig).
Feladat. A város Königsberg (Kalinyingrád most) volt hét híd a Pregel folyó (2.2 ábra, ahol A -. A bal parton, P - jobb partján, az A és B - A sziget). A feladat a következő volt: ha lehet, séta a városban, menjen át minden híd pontosan egyszer?
Ez a probléma társul egyéb játékokhoz melynek lényege arra a következtetésre jutunk, las körbevághassuk a kontúr egy alak, nem vesz Karandila-sha papíron, és nem körbefutó audio kontúr kétszer, azaz „Rajzolj egy kádban egy csapásra.” Az ilyen áramkörök alkotják az úgynevezett faggyúmirigy unikur grafikonok.
A probléma a hidak Königsberg Euler töltötte az egész tanulmány született, amely 1736-ban mutatták be a szentpétervári Tudományos Akadémia tagja.
2.3 ábra mutatja egy grafikon megfelelő a problémát, a Koenigs-Bergischen hidak. Be kell bizonyítanunk, hogy ez a grafikon unikur zsíros.
Ehhez figyelembe vesszük a koncepció a felső index - az élek száma közelít a tetején, és azt mutatják, hogy a következő tétel érvényes.
Tétel. Unicursal grafikon a csúcsok száma páratlan index értéke nulla vagy kettő.
Bizonyítás. Valóban, ha a gráf unikursalen, és nem esik egybe a vég kezdete, a kezdet és a vég az egyetlen csúcsot páratlan index. A maradék csúcsok egy még indexet, mint minden pont és kijutunk belőle. Ha a start egybeesik a végén a csúcsok páratlan index nélkül.
Most viszont, hogy a megoldást a problémára. Definiáljuk a paritás felsők Gras-F ábra 2.3. Vertex A-nak egy index 5, B - 3, n - 3 és N - 3. Így van négy csúcsa páratlan indexű, és ennek következtében-TION, ez a grafikon nem unicursal. Ez azt jelenti, hogy közben egy sétát a város nem csak egyszer halad át mind a hét hidak.
1. Draw grafikonok, amelynek csúcsai a indexek 1, 2, 3 és 4.
2. Rajzolj egy grafikont, amelyben minden csúcs van egy index egyenlő: a) két; b) három; c) négy.
3. Mutassuk meg, hogy bármely oszlop összege az indexek az összes csúcs - páros kétszeresével egyenlő az élek számát. Nyomtató következtet, hogy a csúcsok száma páratlan indexek még.
4. A 6. oszlopban csúcsok, amelyek mindegyike egy index 3. Hány bordák ez? Rajzolj egy gráf.
5. Az 5. oszlop csúcsa, amelyek mindegyike egy index 4. Hogyan volt a bordák? Rajzolj egy gráf.
6. Lehet csatlakozni hét hosszúságú pontok úgy, hogy minden egyes pontszerű volt kötve simán: a) két; b) három; c) négy; d) a másik öt?
7. Írjuk fel és oldja meg a problémát, a kettős probléma 5.
8. A hivatal 15 számítógéppel. Lehetséges, hogy kösse össze őket egymással úgy, hogy minden össze van kötve pontosan a másik három?
9. Az állami 100 városban. Egyes városok elhagyja négy út. Hány utak az állam?
10. Határozza meg, hogy a grafikonok ábrán látható 2.4, vannak unicursal?
11. azt mutatják, hogy minden oszlopban, amelynek élei szegmensek van legalább két csúcs azonos index.
12. Mi a legkisebb számú hidak a probléma a Königsberg híd már menni kétszer megy át minden híd?
13. Bizonyítsuk be, hogy ha a probléma a Königsberg híd újabb híd bárhol a Pregel folyó, a kapott gráf lesz unicursal.