4. grafice Euler.
Am spus deja că, istoric vorbind, teoria grafurilor (precum și topologie) sa născut în rezolvarea puzzle-uri Euler, în care doriți să atragă un accident vascular cerebral pe curbe închise avionul încercuind fiecare site exact o dată.
Definiția 24. Calea Euler într-un grafic este calea care conține toate marginile graficului.
Definiția 25. Un ciclu Euler într-un grafic este un ciclu care conține toate margini ale graficului.
Definiție 26. Un grafic cu ciclul Euler. se numește un grafic Euler.
Teorema 2. Dacă graficul are un ciclu Euler, atunci acesta este conectat.
Exemple de grafice Euler:
1) planul expoziției, dacă exponatele se află pe ambele părți ale sălilor, adică. puteți crea un astfel de traseu închis care, pentru fiecare sală, va permite vizitatorului să treacă exact de două ori - câte unul pe fiecare parte în direcții diferite.
2) Orice oraș poate fi bypassed, trecând prin fiecare stradă exact de două ori - câte unul în fiecare direcție.
3) Figura arată schema zoologică. Vârfurile graficului sunt intrarea, ieșirea, intersecțiile, întoarcerile, capătul mort. Ribele sunt pistele de-a lungul cărora sunt situate celulele. Găsiți un traseu pe care ghidul putea să dețină vizitatori, arătându-le toate animalele și nu trecând mai mult de o singură secțiune a drumului.
Notă. Modul de a ocoli toate marginile graficului poate fi folosit, de exemplu, pentru a găsi o cale care vă permite să ieșiți din labirint. Dacă se știe că toți "pereții" labirintului sunt conectați unul cu celălalt, adică nu există rute închise pe care este posibil să se întoarcă la punctul de plecare, atunci un astfel de labirint poate fi întotdeauna ocolit prin atingerea peretelui cu o mână, de exemplu cea dreaptă.
Există o regulă Rămîi (matematician francez) - de obicei ocoli oricare din labirint - să fie obținerea în orice intersecție O prima dată ca o cale în traversarea labirint. când vă întoarceți la această intersecție A, evitați să folosiți calea a cât mai mult posibil; și numai în acel caz mergeți pe drum și în direcția opusă, când toate celelalte căi de la A vor fi traversate de două ori.
Teorema 3. Pentru ca graficul conectat (multigraf) să fie Euler, este necesar și suficient ca gradele tuturor vârfurilor sale să fie uniforme.
Notă. Această teoremă ne permite să rezolvăm problema a șapte poduri Koenigsberg.
Rezolvarea problemei a șapte poduri Konigsberg.
În studiul problemei: este posibil să se găsească un astfel de traseu care să se încheie pe același țărm unde a început, să treacă prin toate punțile, dar pe fiecare pod numai o singură dată?
În ceea ce privește teoria grafurilor, această problemă poate fi formulată după cum urmează: este multigrafia a șapte Koenigsberg care unește un grafic Euler?
Să găsim gradele vârfurilor. Gradul A = 3, art. B = 5, art. D = 3, art. C = 3.
Din Teorema 3 rezultă că acesta este un multigraf al non -ilers, deoarece vârfurile sale au un grad ciudat. Din aceeași teoremă vedem cum să completăm graficul, că va deveni Eulerian.
Răspuns. O astfel de cale nu există.
4. Grafice bipartite.
Definiția 27. Un grafic este numit bipartit. dacă mulțimea vârfurilor sale V poate fi împărțită în două subseturi disjuncte V1 și V2. că nici două vârfuri din același subset nu sunt îmbinate cu marginile.
Notă. Pentru a accentua faptul că acest grafic este bipartit, vârfurile sale pe diagramă au rânduri sau coloane paralele:
Graficele de seif D sunt utile atunci când obiectele studiate sunt împărțite în două grupuri, astfel încât în cadrul grupurilor interacțiunile de interes sunt absente. În genetică, de exemplu, pot fi semne și gene, în demografie - persoane de sex diferit, în ecologie - prădători și victime, în economie - producători și consumatori etc.
Definiție 28. Un grafic bipartit este numit grafic complet bipartit. dacă fiecare vârf V1 este conectat la fiecare vârf V2.
Nu este întotdeauna ușor de determinat prin forma unui graf grafic dacă un grafic dat este bipartit. La urma urmei, nu este necesar ca vârfurile graficului bipartit să fie plasate în două linii paralele. De exemplu, orice lanț simplu neînchis este un grafic bipartit, ca orice copac.
Teorema 4. Un grafic este bipartit dacă și numai dacă toate ciclurile sale simple au o lungime uniformă. (Cicluri simple - toate nodurile sunt diferite, vârfurile inițiale și finale coincid)
Cu grafurile bipartite, problema asociată este asociată. Să existe mai multe locuri de muncă pentru constructori, mai multe pentru lăcătuși, un număr de locuri pentru pictori, montatori etc. - numai m locuri de muncă. Pe de altă parte, există n solicitanți. Și, unii dintre reclamanți au mai multe profesii. Este posibil ca toți solicitanții să lucreze și fiecare dintre ei să ofere un post în conformitate cu formarea profesională?
Este clar că acest lucru nu se poate face întotdeauna. Mai întâi, d. B. m ≥ n. Dar acest lucru nu este de ajuns, de exemplu, trei locuri pentru instalator și un loc pentru constructor sunt vacante. Apoi, grupul format din doi constructori și un lucrător de construcții - instalator, nu poate fi pus la dispoziție cu muncă. Unul dintre constructori va fi neocupat.
Formăm problema în ceea ce privește graficele. Fie V1 setul de solicitanți, V2 - setul de locuri de muncă vacante. Vârful a al lui V1 este conectat printr-o margine cu vârful b din V2. dacă solicitantul este capabil să preia locul de muncă b. Apoi, obținem un grafic bipartit G (Figura 9). Problema noastră este să extragem subgraful G1 din acest grafic. constând din componente în fiecare dintre care doar două noduri, iar aceste vârfuri sunt conectate printr-o muchie (Figura 10). G1 este un subgraf al întâlnirilor.
Teorema 5 (condiția necesară și suficientă pentru existența unui subgraf de destinație)
Fie mulțimea V1 a graficului B bipartit să conțină n noduri. Pentru ca graficul G să conțină un subgraf al atribuțiilor G1. Este necesar și suficient pentru orice subset. conținând vârfuri k, k = 1,2, ..., n. k sunt descoperite nodele V2. fiecare dintre acestea fiind conectat printr-o margine cu cel puțin un vârf din A.
În ceea ce privește sarcina inițială, aceasta înseamnă că, indiferent de grupul de candidați pe care îi luăm, există poziții k, fiecare dintre acestea putând ocupa cel puțin o persoană din grupul luat.
Observația 1. Restricția m ≥ n poate fi eliminată și a fost studiată câte și care subgrafe ale asignărilor cu acest sau acel număr de componente pot fi formate dintr-un grafic bipartit dat și așa mai departe.
REMARK 2. Matematicianul german Hermann Weil a numit problema de alocare problema nunților din sat. În interpretarea sa de V1 și V2 - acest set de fete și băieți care trăiesc într-un sat și marginile graficului înseamnă că băiatul și fată sunt familiare (sau simpatic) unul cu celălalt. Dorind să oferim fiecărei fete un mire de la mulți tipi familiare (sau simpatic), va trebui să găsim în acest grafic bipartit un sub-program al întâlnirilor.
REMARK 3. Ca și grafice bipartite, putem considera tri-hollow și k-vale cu orice k.
P. 5. Grafice plane și plane.
Printre diagramele izomorfe ale aceluiași grafic se pot găsi diagrame cu marginile care se intersectează nu numai la vârfuri. Unele dintre aceste diagrame pot fi ușor înlocuite cu cele izomorfice, care nu au acest dezavantaj.
Definiție 29. Un grafic este numit planar dacă poate fi reprezentat pe planul printr-o diagramă ale cărei muchii se intersectează numai la vârfuri.
Diagrama însăși se numește un grafic plat.
Notă. Unele grafice pot fi desenate pe un plan, astfel încât marginile lor să nu aibă puncte comune, cu excepția vârfurilor care le aparțin; alții nu pot fi desenați așa. Din acest motiv, graficele individuale pot fi considerate ca hărți geografice, reprezentate pe plan sau sferă.
Definiția 30. Dacă un grafic planar este pur și simplu conectat, atunci graficul său planar este numit hartă.
În figura A) nu este un grafic plat. În Fig. b) același grafic este afișat, numai plat.
În Fig. c) nu este prezentat un grafic planar, în Fig. d) este o hartă grafică izomorfă plană. Spre deosebire de hărțile geografice, un grafic plat conectat poate avea noduri pendante.
Luați în considerare harta unui grafic.
Definiție 31. O limită într-o reprezentare plată a unui grafic este o parte a planului delimitată de un ciclu simplu și care nu conține alte cicluri.
În Fig. a) (1,2,4,1) nu este o față, deoarece conține în ea însăși (1,2,3,1). În grafic există patru fețe: (1,7,4,1), (1,4,2,3,1), (1,2,3,1), (2,6,5,4,2,2).
În figura B) (1,2,3,4,1) este o față, deoarece marginea (4,5) nu formează un ciclu.
Definiția 32. Un ciclu care cuprinde toate fețele interne se numește limita exterioară a hărții. Setul de puncte ale planului situate în afara acestui ciclu se numește limita feței exterioare.
Notă. Orice poliedru tridimensional convex poate fi asociat cu o hartă a cărei margini și fețe, inclusiv cea exterioară, corespund marginilor și fețelor poliedrului.
Teorema 6. Pentru orice hartă, numărul de vârfuri (B), numărul de muchii (P) și numărul de fețe ale hărții (T), inclusiv exteriorul, sunt conectate prin egalitate: B + F = P = 2
Teorema 7. Graficul grafic bipartit complet U3,3 și graficul complet U5 sunt nonplanari.
Teorema 8. Pentru ca graficul G să fie planar, este necesar și suficient ca acesta să nu conțină un subgraf care ar putea fi redus la U3.3 sau U5.
Exemplu (problema celor trei case și trei godeuri)
Într-un sat aproape de trei case sunt trei puțuri. În momente diferite ale anului se dovedește a fi unul sau altul (în căldura unul dintre puțuri se usucă, în îngheț unul dintre ele îngheață etc.). Prin urmare, fiecare casă ar trebui să fie conectată printr-o cale cu fiecare puț și căile se intersectează reciproc. Cu aceasta, proprietarii de case au fost ușor de împăcat, în timp ce ei au trăit în prietenie. Dar ei s-au certat și toată lumea a vrut să aibă drumuri proprii spre puțurile care nu se intersectează cu căile vecinilor. Este posibil să se construiască astfel de căi?
Rezolvăm această problemă cu ajutorul graficelor. Denumim vârfurile graficului ca a1. a2. a3. b1. b2. b3. unde a1. a2. a3 - acasă, b1. b2. b3 - godeuri. Între grupul vertex a1. a2. a3 și grupul vertex b1. b2. b3 există o corespondență. Din fiecare vârf, trei margini ajung la vârfurile corespunzătoare. Prin condiția problemei, avem un graf bipartit complet U3,3 cu marginile intersectate. Este posibil să se construiască un graf plat, izomorf la graficul U3.3. Cu alte cuvinte, graficul U3,3 este planar?
Graficul bipartit U3.3 are forma. Din teorema 7 rezultă că acest grafic nu este planar. Ie așezarea unor căi care nu se suprapun imposibil!
Notă. Șinele ar putea fi aranjate disjoint dacă una dintre case ar putea fi ridicată deasupra solului. Cu alte cuvinte, dacă nodurile acestui grafic nu sunt plasate într-un plan, ci în spațiul tridimensional, muchiile sale nu se vor intersecta. Această proprietate este inerentă în orice grafic.
Articole similare
Trimiteți-le prietenilor: