Cifra formată dintr-un set finit de puncte ale planului și segmente care leagă unele dintre aceste puncte se numește un grafic plat. sau pur și simplu un grafic (Figura 2.1, a). Punctele sunt numite noduri. iar segmentele sunt marginile graficului.
În locul segmentelor, liniile curbate în plan sunt de asemenea considerate marginile grafurilor (Figura 2.1, b).
Exemple de grafice sunt metroul, schemele de căi ferate și de autostrăzi, planurile de expoziții etc. Graficele indică diferitele relații dintre obiecte.
Din punct de vedere istoric, teoria grafurilor a provenit din soluția puzzle-urilor acum două sute de ani.
O astfel de problemă de puzzle a fost problema podurilor din Königsberg, care a atras atenția Leonhard Euler (1707-1783), o lungă perioadă de timp a trăit și a lucrat în Rusia (1727-1741 și de la 1766 până la moartea sa).
Sarcina. În orașul Königsberg (Kaliningrad acum) a avut șapte poduri peste râul pregelului (Figura 2.2, unde A este -. Malul stâng, P - malul drept, A și B - a insulei). Problema a fost aceasta: este posibil, mergând prin oraș, să treci prin fiecare pod exact o dată?
Această problemă este asociată cu alte puzzle-uri a căror esență concluzionăm-las să taie în jurul valorii de conturul unei figuri, fără a lua Karandila-sha pe hârtie și nu încercuind contur audio de două ori, și anume "trageți într-o singură lovitură." Astfel de contururi formează așa-numitele grafice unicour-siale.
Problema podurilor Koenigsberg L. Euler a dedicat un întreg studiu, care în 1736 a fost prezentat Academiei de Științe din Sankt Petersburg.
Figura 2.3 prezintă un grafic care corespunde problemei punților Koenigsberg. Este necesar să se demonstreze că acest grafic este unicircular.
Pentru a face acest lucru, luăm în considerare conceptul indexului unui vârf - numărul de muchii unui graf convergând la un anumit vertex, și demonstrăm că teorema următoare este valabilă.
Teorema. Pentru un grafic unicursal, numărul de noduri ale unui indice ciudat este zero sau două.
Dovada. Într-adevăr, dacă graficul este unicursal și originea sa nu coincide cu sfârșitul, atunci începutul și sfârșitul sunt singurele noduri ale indexului ciudat. Vârfurile rămase au un index par, din moment ce intrăm și ieșim din fiecare punct. Dacă începutul coincide cu sfârșitul, atunci nu există noduri cu un indice ciudat.
Să trecem acum la rezolvarea problemei. Definim paritatea vârfurilor graficului din figura 2.3. Vârful A are indexul 5, B - 3, P - 3 și A - 3. Astfel, avem patru noduri de indice ciudat și, prin urmare, graficul dat nu este unicursal. Prin urmare, obținem că într-o plimbare în jurul orașului nu se poate trece prin fiecare dintre cele șapte poduri o singură dată.
1. Desenați grafice care au noduri de indicii 1, 2, 3 și 4.
2. Desenați un grafic în care fiecare vârf are un indice egal cu: a) două; b) trei; c) patru.
3. Dovedeste ca, in orice grafic, suma indiciilor tuturor nodurilor sale este un numar par echivalent cu dublul numarului de margini al graficului. De aici rezultă că numărul de noduri cu indici ciudați este egal.
4. În coloana 6 de vârfuri, fiecare dintre ele având un indice de 3. Câte margini are? Desenați un astfel de grafic.
5. În coloana 5 de noduri, fiecare dintre ele având un index de 4. Câte margini are? Desenați un astfel de grafic.
6. Este posibil să conectați șapte puncte pe segmente astfel încât fiecare punct să fie conectat exact cu: a) două; b) trei; c) patru; d) de alte cinci persoane?
7. Formulează și rezolvă probleme care sunt duale la probleme.
8. În birou există 15 calculatoare. Poți să le conectezi între ele, astfel încât toată lumea să fie conectată exact cu ceilalți trei?
9. Există 100 de orașe în stat. Din fiecare oraș există patru drumuri. Câte drumuri în stat?
10. Determinați ce grafice din Figura 2.4 sunt unicursal?
11. Să demonstreze că în fiecare grafic a cărui margini sunt segmente există cel puțin două vârfuri ale aceluiași index.
12. Care este cel mai mic număr de poduri în problema podurilor Koenigsberg, de care va trebui să treci de două ori pentru a traversa fiecare pod?
13. Dovedește că, dacă problema podurilor Königsberg adăuga un alt pod oriunde în râul Pregelul, graficul rezultat va fi unicursal.
Articole similare
Trimiteți-le prietenilor: