A gráf fogalma a matematikában - absztrakt, 3. oldal
4. Euler grafikonok.
Már mondta, hogy történelmileg gráfelmélet (valamint topológia) született megoldása Euler nehézség, amelyben szeretné felhívni a stroke a zárt görbe sík köröztek minden helyszínen pontosan egyszer.
Definíció 24. A grafikon Euler pálya az a görbe, amely a grafikon összes széleit tartalmazza.
Definíció 25. Egy grafikon Euler ciklusa egy ciklus, amely a grafikon minden széleit tartalmazza.
Definíció 26. Egy grafikon Euler ciklussal. egy Euler gráfnak nevezik.
2. Tétel. Ha a grafikon Euler-ciklussal rendelkezik, akkor csatlakoztatva van.
Példák Euler grafikonokra:
1) a kiállítási terv, ha a kiállítás a csarnok mindkét oldalán található, pl. olyan zárt útvonalat hozhat létre, amelyet minden egyes csarnoknál a látogató pontosan kétszer képes átjutni - mindegyik oldalon különböző irányokban.
2) Bármelyik város megkerülhető, minden egyes utcán pontosan két alkalommal - minden irányban.
3) Az ábra mutatja az állatkert rendjét. A grafikon teteje a bejárat, a kilépés, a kereszteződések, a fordulók, a zsákutcák. A bordák azok a sávok, amelyek mentén a sejtek találhatók. Keresse meg az útvonalat, amelyen az útmutató tartogathatja a látogatókat, megmutatva nekik az összes állatot, és nem haladhatja meg többször az út egyetlen szakaszát.
Megjegyzés. A gráf összes széleinek megkerülését úgy lehet használni, hogy például megtalálja azt az utat, amely lehetővé teszi, hogy kilépjen a labirintusból. Ha ismert, hogy a labirintus "falai" egymáshoz kapcsolódnak, pl. nincsenek zárt útvonalak, amelyeken vissza lehet térni a kiindulási pontra, akkor egy ilyen labirintus mindig megkerülhető úgy, hogy egy kézzel, például a jobb oldallal érintkezik a falzal.
Tarrynak (a francia matematikusnak) van szabálya - a labirintus megkerülésének szabálya - amikor egy labirintus elhaladása következik, az A kereszteződésbe esik először egy bizonyos út mentén. ha visszatér ezen A kereszteződéshez, ne használja az a útvonalat, ameddig csak lehetséges; és csak ebben az esetben az út mentén és az ellenkező irányba halad, amikor az A-tól való minden más útvonalat kétszer megkerül.
Tétel 3. Annak érdekében, hogy a kapcsolt grafikon (multigraph) legyen Euler, szükséges és elegendő, hogy minden csúcsa fokozat egyenletes legyen.
Megjegyzés. Ez a tétel lehetővé teszi számunkra, hogy megoldjuk a hét Koenigsberg-hidat.
A hét Konigsberg-híd problémájának megoldása.
A probléma felmérésében: lehetséges-e egy olyan utat találni, amely ugyanazon a parton végződik, ahol elkezdődött, áthalad az összes hidakon, de minden hídon csak egyszer?
A grafikonelmélet szempontjából ez a probléma a következőképpen fogalmazható meg: a hét Koenigsberg-sáv többlépcsője Euler gráfot?
Nézzük meg a csúcsok fokát. A = 3 fokozat, sz. B = 5, art. D = 3, art. C = 3.
A 3. tételből következik, hogy ez a többlépcsős nem-pótkocsik, mivel csúcsainak furcsasága van. Ugyanezen tételből láthatjuk, hogyan egészítsük ki a grafikont, hogy Eulerianak váljon.
Válasz. Egy ilyen út nem létezik.
4. Kétoldalú grafikonok.
Meghatározás 27. A gráfot bipartitnak nevezik. ha V csúcsainak halmaza két ilyen diszjunktusos V1 és V2 részhalmazra osztható. hogy az ugyanazon alcsoport két csúcsa nem csatlakozik élekhez.
Megjegyzés. Annak hangsúlyozása érdekében, hogy ez a grafikon kétpólusú, csúcspontjai a diagramon párhuzamos sorokkal vagy oszlopokkal rendelkeznek:
A D-pult grafikonok akkor hasznosak, ha a vizsgált tárgyak két csoportra vannak osztva, így a csoportokon belül a kölcsönhatások hiányoznak. A genetikában például jelek és gének lehetnek, demográfiában - különböző neműek, ökológia - ragadozók és áldozatok, a gazdaságban - termelők és fogyasztók stb.
Definíció 28. A kétpárti gráfot teljes kétpárti gráfnak nevezik. ha minden V1 csúcs minden V2 csúcsra csatlakozik.
Nem mindig könnyű meghatározni grafikon formájában, hogy egy adott gráf kétpárti. Végül is nem szükséges, hogy a kétpárti grafikon csúcsai két párhuzamos vonalban helyezkedjenek el. Például bármely egyszerű, zárt lánc kétpólusú gráf, mint bármelyik fa.
Tétel 4. Egy grafikon kétpólusú, ha és csak akkor, ha minden egyszerű ciklusának egyenlőnek kell lennie. (Egyszerű ciklusok - az összes csúcs különböző, a kezdeti és a végső csúcs egybe esik)
Kétpárti grafikonokkal a hozzárendelési probléma kapcsolatban áll. Legyen több munkahely az építõknek, többet a lakatosoknak, néhány helyet a festõknek, szerelõknek stb. - csak m munkákat. Másrészről nincs n pályázó. És egyes pályázóknak több szakmája van. Lehetséges-e minden pályázónak munkát végezni, és mindegyiket szakmai képzettségének megfelelő álláshely biztosítására?
Nyilvánvaló, hogy ez nem mindig lehetséges. Először d. B. m ≥ n. De ez nem elég, például három hely a telepítő számára, és egy hely az építtetőnek üres. Ezután a két építőből és egy építőmunkás-szerelőből álló csoport nem tud munkát végezni. Az egyik építtető üres lesz.
A problémát grafikonok formájában fogalmazzuk meg. Legyen V1 a pályázók halmaza, V2 - az üres álláshelyek halmaza. A V1 a csúcsát egy B csúcsú perem csatlakozik a V2-ből. ha a pályázó képes a munkahelyre. b. Ezután egy kétpólusú G gráfot kapunk (9. ábra), a probléma az, hogy kivonjuk a G1 szubgráfot ebből a grafikonból. amelyek mindegyikében csak két csúcsot tartalmaznak, és ezeket a csúcsokat egy peremmel összeköti (10. ábra). A G1 a kinevezések részhalmaza.
Tétel 5 (szükséges és elégséges feltétel egy rendeltetési subgraph létezésére)
Hagyja, hogy a kétpárti G grafikon V1-e tartalmazzon n csúcsot. Annak érdekében, hogy a G gráf tartalmazza a G1 hozzárendelések részgrafikáját. Szükséges és elégséges minden alcsoport esetében. amely k csúcsokat tartalmaz, k = 1,2, ..., n. k V2 csúcsok találhatók. amelyek mindegyike legalább egy A-csúcsú peremmel van összekötve.
Ami a kezdeti feladatot illeti, ez azt jelenti, hogy függetlenül attól, hogy melyik k-pályázó csoportot veszünk, vannak olyan k pozíciók, amelyek mindegyike képes legalább egy embert elfoglalni a csoportból.
Megjegyzések 1. A korlátozást m ≥ n eldobhatjuk, és megvizsgáljuk, hogy hányan és mely részösszegekből származik ez a vagy az adott komponensek száma egy adott kétpártú gráfból stb.
MEGJEGYZÉS 2. Hermann Weil német matematikus felhívta a feladási problémát a falusi esküvők problémájára. V1 és V2 értelmezésében - egy faluban élő lányok és fiúk, és a grafikon élei azt jelentik, hogy a fiú és a lány egymással ismerősek (vagy szimpatikusak). Annak érdekében, hogy minden egyes leányt több ismerős (vagy szimpatikus) srác közül vőlegessé tegyünk, ebben a kétpárti gráfban a találkozók alprogramját kell találnunk.
MEGJEGYZÉS 3. Mint a kétpárti grafikonok, három-üreges és k-völgyet is vizsgálhatunk minden k-vel.
P. 5. Planáris és sík grafikonok.
Ugyanazon grafikon izomorf diagramjai között olyan diagramok láthatók, amelyeknek élei nemcsak a csúcsokon metszenek. Ezen diagramok közül néhány könnyen helyettesíthető izomorfokkal, amelyeknek nincs ilyen hátrányuk.
Meghatározás 29. A gráfot síknak nevezzük, ha síkban ábrázolható egy olyan diagrammal, amelynek élei csak a csúcsokon metszenek.
A diagramot sík grafikonnak nevezik.
Megjegyzés. Néhány grafikon rajzolható egy síkra úgy, hogy a széleiknek nincs közös pontja, kivéve a hozzájuk tartozó csúcsokat; mások nem vonhatók így. Emiatt az egyes grafikonok földrajzi térképnek tekinthetők, egy síkon vagy gömbön ábrázolva.
Definíció 30. Ha egy sík grafikon egyszerűen összekapcsolódik, akkor sík gráfját térképnek nevezik.
Az A) ábrán nem egy sík grafikon. Az 1. ábrán. b) ugyanaz a grafikon látható, csak lapos.
Az 1. ábrán. c) nem ábrázolt sík grafikon, a 3. ábrán. d) izomorf sík grafikon térkép. A földrajzi térképektől eltérően a lapos, egyszerűen összekapcsolt grafikonon lehet függőleges csúcspont.
Tekintsük a grafikon térképét.
Definíció 31. A gráf sík ábrázolásának határa egy egyszerű ciklus által határolt és más ciklusokat nem tartalmazó sík része.
Az 1. ábrán. a) (1,2,4,1) nem arc, mivel önmagában tartalmaz (1,2,3,1). A gráfban négy arc található: (1,7,4,1), (1,4,2,3,1), (1,2,3,1), (2,6,5,4,2,2).
A B) ábrán (1, 2, 3, 4, 1) egy arc, mivel a perem (4,5) nem képez ciklust.
Definíció 32. Az összes belső arcot körülvevő ciklus a térkép külső határa. A sík ezen a cikluson kívül fekvő síkjait a külsõ felület határának nevezik.
Megjegyzés. Minden konvex háromdimenziós poliéder társítható egy térképhez, amelynek élei és arca, beleértve a külsőet is, megfelelnek a poliéder széleinek és arcainak.
6. tétel. Minden térkép esetében egyenlõséggel kötõdik a B csúcspont, a szélek száma (P) és a térkép (T), beleértve a külsõ felületet is: B + F = P = 2
Tétel 7. Az U3,3 teljes kétpárti grafikon és az U5 teljes grafikon nemplanáris.
Tétel 8. Annak érdekében, hogy a G gráf sík legyen, szükséges és elegendő, hogy ne tartalmazzon olyan subgraphot, amely szűkíthető U3.3 vagy U5-re.
Példa (három ház és három kutak problémája)
Egy házban három ház három kút. Különböző időpontokban az év áll rendelkezésre, hogy az egyik vagy a másik is (a hő egyik cseppmentesítse és fagy némelyikük fagyasztjuk, és így tovább. D.). Ezért minden házat össze kell kötni egy ösvényrel minden lyukkal, és az ösvények metszi egymást. Ezzel háztartások könnyen elviselhető, míg élt barátság. De itt volt egy esik ki, és mindenki szeretett volna a saját út a kutak, amelyek nem metszik utak szomszédok. Lehetséges ilyen utakat felépíteni?
Ezt a problémát grafikonok segítségével oldjuk meg. A gráf csúcspontjait a1-nek nevezzük. a2. a3. b1. b2. b3. ahol a1. a2. a3 - otthon, b1. b2. b3 - kutak. Az a1 csúcscsoport között. a2. a3 és a b1 csúcscsoport. b2. b3 van egy levelezés. Minden csúcsról három széle megy a megfelelő csúcsokhoz. A probléma állapota mellett egy teljes kétpólusú, U3,3 grafikon van, metszőélekkel. Lehetséges-e egy sík grafikon létrehozása isomorf az U3.3 grafikonra. Más szóval, az U3,3 gráf sík?
Az U3.3 kétpólusú grafikonnak van forma. A 7. Tételből következik, hogy ez a gráf nem sík. Ie fekvő nem átfedő utakat lehetetlen!
Megjegyzés. A pályák elkülöníthetőek, ha az egyik ház felemelhető a talaj felett. Más szavakkal, ha a grafikon csúcsai nem egy síkban vannak elhelyezve, hanem háromdimenziós térben, az élei nem metszik egymást. Ez a tulajdonság minden grafikonban rejlik.