Care este metoda graficelor?
Cuvântul "grafic" în matematică înseamnă o imagine în care sunt desenate mai multe puncte, unele dintre ele fiind conectate prin linii. În primul rând, trebuie spus că graficele care vor fi discutate aristocraților din trecut nu au nimic de-a face. "Graficele" noastre au cuvântul grecesc rădăcină "grapho", adică "eu scriu". Aceeași rădăcină în cuvintele "program", "biografie".
În matematică, definiția unui grafic este după cum urmează: un grafic este un set finit de puncte, dintre care unele sunt legate prin linii. Punctele se numesc nodurile graficului, iar liniile de conectare se numesc marginile.
O schemă de grafic constând din vârfuri "izolate" se numește un grafic zero. (Figura 2)
Graficele în care nu sunt construite toate marginile posibile sunt numite grafice incomplete. (Figura 3)
Graficele în care sunt construite toate marginile posibile sunt numite grafice complete. (Figura 4)
Un grafic, fiecare vertex al căruia este conectat la o margine a oricărui alt vârf, se spune că este complet.
Rețineți că dacă graficul complet are n noduri, numărul de margini este egal cu
Într-adevăr, numărul de muchii într-un grafic complet cu n noduri definite ca numărul de perechi neordonate compus din toate n-puncte de marginile graficului, adică numărul de combinații de n elemente 2 ..:
Un grafic care nu este complet poate fi completat complet cu aceleași vârfuri, adăugând marginile lipsă. De exemplu, Figura 3 prezintă un grafic incomplet cu cinci noduri. În figura 4, marginile care convertesc un grafic într-un grafic complet sunt reprezentate de o altă culoare, setul de vârfuri ale unui grafic cu aceste margini se numește complementul unui grafic.
Grade de vârfuri și numărarea numărului de muchii.
Numărul de margini emise de la vârful unui grafic este numit gradul unui vârf. Vârful unui grafic cu un grad ciudat este numit impar. și un grad chiar - chiar.
Dacă gradele tuturor vârfurilor graficului sunt egale, atunci se spune că graficul este omogen. Astfel, orice grafic complet este omogen.
Figura 5 prezintă un grafic cu cinci noduri. Gradul vârfului A este notat de St. A.
În figură. St.A = 1, St.B = 2, St.V = 3, St.G = 2, Std.D = 0.
Să formuleze niște regularități inerente în anumite grafice.
Gradele vârfurilor graficului complet sunt aceleași și fiecare dintre ele este una mai mică decât numărul de vârfuri din acest grafic.
Acest model este evident după luarea în considerare a oricărui grafic complet. Fiecare vertex este conectat printr-o margine la fiecare vertex, cu excepția ei însăși, adică, de la fiecare vârf al grafului având n noduri, o n-1 margine emană, care urma să fie dovedită.
Suma gradelor vârfurilor unui grafic este egală cu egal cu dublul numărului de margini ale graficului.
Acest model este valabil nu numai pentru graficul complet, ci pentru orice grafic. dovada:
Într-adevăr, fiecare margine a graficului conectează două vârfuri. Deci, dacă vom adăuga până la numărul de grade de toate nodurile din grafic, vom obține de două ori numărul de muchii 2R .. (R - numărul de muchii), care la fiecare margine a fost numărat de două ori, după cum este necesar
Numărul de vârfuri ciudate ale oricărui grafic este egal. dovada:
Luați în considerare un grafic arbitrar Γ. Să presupunem că în acest grafic numărul de vârfuri al căror grad 1 este egal cu K1; numărul de vârfuri din gradul 2 este egal cu K2; ; numărul de noduri al căror grad este n este egal cu Kn. Apoi, suma gradelor vârfurilor acestui grafic poate fi scrisă ca
K1 + 2K2 + ZK3 +. + nKn.
Pe de altă parte: dacă numărul de margini ale graficului R, apoi din regularitatea 2 se știe că suma gradelor tuturor vârfurilor graficului este egală cu 2R. Apoi putem scrie o ecuație
K1 + 2K2 + ZK3 +. + nKn = 2R. (1)
Selectăm pe partea stângă a egalității o sumă egală cu numărul de noduri ciudate ale graficului (K1 + K3 +.):
K1 + 2K2 + ZK3 + 4K4 + 5K5 +. + nK = 2R,
(K1 + K3 + K5 +.) + (2K2 + 2X3 + 4K4 + 4K5 +.) = 2R
Cel de-al doilea bracket este un număr par, ca suma numerelor par. Suma rezultată (2R) este un număr par. Prin urmare, (K1 + K3 + K5 +.) Este un număr par.
Să analizăm acum problemele rezolvate cu ajutorul graficelor:
Problema. Primatul clasei. În campionatul de clasă pe tenis de masă 6 participanți: Andrey, Boris, Victor, Galina, Dmitri și Elena. Campionatul se desfășoară pe un sistem circular - fiecare dintre participanți joacă odată cu fiecare dintre celelalte. Până în prezent, unele jocuri au fost deja jucate: Andrei a jucat cu Boris, Galina și Elena; Boris, așa cum am menționat deja, cu Andrei și cu Galina; Victor - cu Galina, Dmitri și Elena; Galina cu Andrey și Boris; Dmitrii - cu Victor și Elena - cu Andrew și Victor. Câte jocuri au fost făcute până acum și cât de mult a rămas?
Discuție. Descriem datele de sarcină sub forma unei diagrame. Participanții vor fi reprezentați prin punctele: Andrew - punctul A, Boris - punctul B, etc. Dacă doi participanți au jucat deja între ei, atunci vom conecta punctele care descriu punctele lor pe segmente. Se obține circuitul prezentat în figura 1.
Punctele A, B, B, D, D, E reprezintă vârful graficului care leagă segmentele - marginile graficului.
Rețineți că punctele de intersecție ale marginilor unui grafic nu sunt vârfurile sale.
Numărul de jocuri jucate până în prezent este egal cu numărul de margini, adică 7.
Pentru a evita confuzia, vârful graficului este deseori reprezentat nu în puncte, ci în cercuri mici.
Pentru a găsi numărul de jocuri pe care trebuie să le efectueze, construi un alt grafic cu aceleași vârfuri, dar coastele se vor conecta participanții care nu au jucat reciproc (figura 2), marginile în acest grafic avansat 8, apoi lăsat să-și petreacă 8 jocuri : Andrew - cu Victor și Dmitri; Boris - Cu Victor, Dmitriu și Elena, etc.
Să încercăm să construim un grafic pentru situația descrisă în următoarea problemă:
Cine joacă Lyapkin-Tyapkin? În cercul de teatru școlar a decis să pună "Inspectorul" lui Gogol. Apoi a izbucnit un argument aprins. Totul a început cu Lyapkin - Tyapkin.
- Lyapkinym - Tyapkinym Voi! Said Gene decisiv.
- Nu, voi fi Lyapkin-Tyapkin, replica Dima. "Am visat din copilărie că această imagine a fost realizată pe scenă".
- Ei bine, e bine să renunț la acest rol, dacă m-au lăsat să joc Khlestakov, - a arătat generozitatea lui Gen.
- ... Și eu - Osip, - nu i-am oferit cu generozitate Dima.
- Vreau să fiu o căpșună sau un guvernator ", a spus Vova.
- Nu, voi fi guvernatorul, - strigă Alik și Borya într-un cor. - Sau Khlestakov, -
au adăugat în același timp.
Rolele vor fi distribuite astfel încât artiștii să fie fericiți?
Discuție. Noi reprezentăm tineri actori din rândul de sus de cercuri: A - Alik, B - Boris, The - Vova, D - Gene, D - Dima, și rolurile pe care le vor juca - cercuri de-al doilea rând (1 - Lyapkin - Tyapkin 2 - Khlestakov 3 - Osip, 4 - Căpșuni, 5 - Guvernatorul). Apoi, de la fiecare participant, tragem segmentele, adică rib, la rolurile pe care ar dori să le joace. Avem un grafic cu zece noduri și zece margini (figura 3)
Pentru a rezolva problema, trebuie să selectați cinci din cinci margini care nu au noduri comune. Faceți-o ușor. Este suficient să notăm că nodurile 3 și 4 sunt conduse de o margine, respectiv de la vârfurile A și respectiv B. Acest lucru înseamnă că Osip (top 3) ar trebui să joace Dima (cine altceva?), Și Zemlyanichka - Vova. Vershina1 - Lyapkin - Tyapkin - conectat cu aripioare D și E. Rib 1 - D plătește, pentru că Dima este deja ocupat, este 1 - F, Lyapkin - Tyapkina pentru a juca Gene. Rămâne să conectăm vârfurile A și B cu nodurile 2 și 5, corespunzătoare rolurilor lui Khlestakov și Gorodnichy. Acest lucru se poate face în două moduri: alegeți marginea A-5 și B-2 sau marginea A -2 și B -5. În primul caz, Alik va juca guvernatorul, iar Boria-Khlestakova, în al doilea caz, dimpotrivă. După cum arată graficul, nu există alte soluții la problemă.
Același grafic va fi obținut la rezolvarea următoarei probleme:
Sarcina. Vecinii calzi. Locuitorii din cinci case au avut o cădere cu unul pe altul, și nu să se întâlnească la fântână, a decis să-i (puțuri) diviza, astfel încât proprietarul fiecare casă a mers la „propria“ starea de bine prin calea sa „proprie“. Vor fi capabili să facă acest lucru?
Se pune întrebarea: au fost atât de necesare graficele din problemele dezasamblate? Nu putem ajunge la o soluție într-un mod pur logic? Da, poți. Dar graficele au dat vizibilitate condițiilor, au simplificat soluția și au relevat similitudinea sarcinilor, transformând cele două sarcini într-una, iar acest lucru nu este atât de mic. Și acum imaginați sarcinile ale căror grafice au 100 sau mai multe noduri. Dar tocmai aceste sarcini trebuie rezolvate de inginerii și economiștii moderni. Aici nu puteți face fără grafice.
III. Graficele lui Euler.
Teoria grafică - știința este relativ tânără: în vremea lui Newton, o astfel de știință nu exista încă, deși au existat "copaci genealogici" în cursul cărora au reprezentat soiuri de grafice. Prima lucrare privind teoria grafurilor aparține lui Leonard Euler și a apărut în 1736 în publicațiile Academiei de Științe din Sankt Petersburg. Această lucrare a început cu luarea în considerare a următoarei sarcini:
a) Problema punților Koenigsberg. Orașul Koenigsberg (acum Kaliningrad) este situat pe malurile și două insule ale râului Pregel (Pregoli). Diferite părți ale orașului au fost conectate prin șapte poduri, după cum se arată în figură. În zilele de duminică, cetățenii fac plimbări în jurul orașului. Este posibil să alegeți o astfel de rută pentru a trece o singură dată pe fiecare pod și apoi să reveniți la punctul de plecare al drumului?
Înainte de a examina soluția acestei probleme, introducem noțiunea de "grafice Euler".
Să încercăm graficul descris în figura 4, cerc cu un singur curs. adică fără a lua creionul din foaia de hârtie și care nu trec prin aceeași parte a liniei de mai multe ori.
Această figură, atât de simplă înfățișată, se pare, are o caracteristică interesantă. Dacă începem mișcarea de la vârful B, atunci cu siguranță o vom obține. Și ce se întâmplă dacă începem de la A? Este ușor să ne asigurăm că în acest caz nu putem face cercuri: vom avea mereu coaste necontrolate care nu pot fi atinse.
În Fig. Figura 5 prezintă un grafic pe care probabil îl puteți desena cu o singură lovitură. Este o stea. Se pare că, deși pare mult mai complicat decât graficul anterior, puteți să-l încercați pornind de la orice vârf.
Graficele trasate în figura 6 pot fi de asemenea trase cu un curs al stiloului injector (pen-ului).
Încercați acum să desenați un grafic într-o singură lovitură, prezentată în figura 7
Nu ai reușit! De ce? Nu poți găsi topul potrivit? Nu! Nu este așa. Acest grafic nu poate fi desenat cu lovitura de stilou.
Vom face argumente care ne vor convinge de acest lucru. Luați în considerare nodul A. Trei noduri ieșite din ea. Începem să tragem un grafic din acest vârf. Pentru a trece prin fiecare dintre aceste margini, trebuie să ieșim din partea de sus a lui A de către unul dintre ei, la un moment dat este necesar să ne întoarcem la acesta în a doua și să ieșim pe a treia. Dar din nou nu putem intra! Prin urmare, dacă începem să tragem din vârful A, nu putem termina.
Să presupunem acum că punctul A nu este un început. Apoi, în procesul de desen, trebuie să intrăm într-una din coaste, să mergem diferit și să ne întoarcem la a treia. Și din moment ce nu putem ieși din ea, atunci vârful A în acest caz ar trebui să fie sfârșitul.
Deci, vârful A trebuie să fie fie originea, fie ultimul nod al trasării.
Dar putem spune la fel despre celelalte trei noduri ale graficului nostru. Dar, la urma urmei, vârful inițial al desenului poate fi doar un vertex, iar vârful final poate fi de asemenea doar un vertex! Deci, este imposibil să desenezi acest grafic într-o singură lovitură.
Graficul, care poate fi desenat fără a lua creionul din hârtie, se numește Eulerian (figura 6).
Aceste grafice sunt numite după omul de știință Leonard Euler.
Zakonomernost1. (rezultă din teorema noastră).
Este imposibil să se elaboreze un grafic cu un număr impar de vârfuri ciudate.
Regularitatea 2.
Dacă toate vârfurile graficului sunt egale, atunci nu puteți să luați creionul din hârtie (cu "o singură lovitură"), trasând pe fiecare margine o singură dată, pentru a desena acest grafic. Puteți începe mișcarea din orice vârf și terminați-o în același vârf.
Regularitatea 3.
Un grafic care are doar două noduri impare pot fi trase fără a ridica creionul pe hârtie, mișcarea trebuie să înceapă cu una dintre aceste noduri impare, iar al doilea capăt al acesteia.
Regularitatea 4.
Un grafic cu mai mult de două vârfuri ciudate nu poate fi desenat "într-o singură lovitură".
O figura (grafic) care poate fi desenată fără a lua un creion din hârtie se numește unicursal.
Se spune că un grafic este conectat dacă oricare dintre două vârfuri poate fi conectat printr-o cale, adică o secvență de margini, fiecare dintre ele începând de la sfârșitul celei anterioare.
Un grafic este numit deconectat dacă această condiție nu este îndeplinită.
În Figura 7, evident, este prezentat un grafic disjunctiv. Dacă, de exemplu, tragem o margine între vârfurile lui D și E, atunci graficul devine conectat. (Fig.8)
O astfel de margine în teoria grafurilor (după eliminarea căreia graficul dintr-o conexiune se transformă într-un grafic deconectat) se numește o punte.
Exemple de punți din figura 7 ar putea fi nervurile DE, A3, BZ, etc., fiecare dintre acestea ar conecta vârfurile părților "izolate" ale graficului (fig.8)
Graficul grafic incoerent cuprinde mai multe "piese". Aceste "piese" sunt numite componentele conexiunii graficului. Fiecare componentă conectată este, bineînțeles, un grafic conectat. Rețineți că un grafic conectat are o componentă conectată.
Teorema.
Un grafic este Euler dacă și numai dacă este conectat și are cel mult două noduri ciudate.
Desenând graficul pe fiecare vârf, cu excepția primului și ultimului, intrăm în același număr de ori pe care l-am lăsat. Prin urmare, gradele tuturor vârfurilor trebuie să fie uniforme, cu excepția a două, și de aceea graficul Euler are cel mult două noduri ciudate.
Să ne întoarcem acum la problema punților Koenigsberg.
Discutarea problemei. Notăm secțiune diferită literele A, B, C, D, și poduri - literele a, b, c, d, e, f, g - punțile de legătură părțile corespunzătoare ale orașului. În această sarcină, există doar puncte de trecere pod: care trece prin orice pod, suntem întotdeauna o parte din noi înșine în altele, și vice-versa, trecând de la o parte din oraș la altul, vom trece cu siguranță peste pod. Prin urmare, descrie planul orașului într-un grafic al cărui vârfuri A, B, C, D (Figura 8) prezintă părți individuale ale orașului, iar marginile a, b, c, d, e, f, g - poduri care leagă secțiunea corespunzătoare a . Este adesea mai convenabil să se reprezinte marginile mai convenabil nu prin linii drepte, ci prin cele curbate prin "arce".
Dacă a existat o rută care satisfăcea starea problemei, atunci ar exista o traversare închisă și continuă a acestui grafic, trecând o dată pentru fiecare margine. Cu alte cuvinte, acest grafic trebuie să fie desenat într-o singură lovitură. Dar acest lucru nu este posibil - indiferent de partea de sus, am ales pentru original, trebuie să treacă prin restul de sus, și, în același timp, fiecare margine „de intrare“ (podul pe care am intrat în această parte a orașului) va corespunde unei „iese“ pod de margine, pe care noi și apoi utilizați pentru a părăsi această parte a orașului): numărul de muchii ce intră în fiecare nod este egal cu numărul de muchii din ea, și anume, numărul total al reuniunii muchiilor la fiecare nod trebuie să fie chiar ... Graficul nostru nu satisface această condiție și, prin urmare, traseul necesar nu există.
Pentru cei care studiază limba engleză