Este recomandabil să introduceți conceptul de graf după ce au fost analizate mai multe probleme similare cu problema 1, considerent decisiv în care este reprezentarea grafică. Este important ca elevii să realizeze imediat că același grafic poate fi desenat în moduri diferite. În opinia mea, nu este nevoie să dau o definiție strictă a unui grafic, deoarece este prea greoaie și nu va face decât să complice discuția. La început, un concept intuitiv va fi suficient. Când discutați despre conceptul de izomorfism, puteți rezolva mai multe exerciții pentru a identifica grafice izomorfe și neizomorfe. Unul dintre punctele centrale ale subiectului este teorema privind paritatea numărului de vârfuri impare. Este important ca studenții să înțeleagă pe deplin dovada acesteia și să învețe cum să o aplice în rezolvarea problemelor. Când analizez mai multe probleme, recomand să nu te referi la teoremă, ci să repeți efectiv demonstrația acesteia. Conceptul de conectivitate grafică este, de asemenea, extrem de important. O considerație semnificativă aici este luarea în considerare a componentei de conectivitate; aceasta trebuie acordată o atenție deosebită. Graficele Euler sunt aproape un subiect de joc.

Primul și principal obiectiv care trebuie urmărit atunci când studiază graficele este de a-i învăța pe școlari să vadă graficul în enunțul problemei și să traducă corect condiția în limbajul teoriei graficelor. Nu ar trebui să le spuneți pe amândouă tuturor în mai multe clase la rând. Este mai bine să împarți cursurile pe 2-3 ani academici. (Atașează desfășurarea lecției „Conceptul de grafic. Aplicarea graficelor la rezolvarea de probleme” în clasa a VI-a).

2. Material teoretic pentru tema „Grafe”.

Introducere

Graficele sunt obiecte matematice minunate; cu ajutorul lor puteți rezolva o mulțime de probleme diferite, în exterior, diferite. Există o întreagă secțiune în matematică - teoria grafurilor, care studiază grafurile, proprietățile și aplicațiile lor. Vom discuta doar cele mai de bază concepte, proprietăți ale graficelor și câteva modalități de rezolvare a problemelor.

Conceptul de grafic

Să luăm în considerare două probleme.

Sarcina 1. Comunicarea spațială a fost stabilită între cele nouă planete ale sistemului solar. Rachetele obișnuite zboară pe următoarele rute: Pământ - Mercur; Pluto - Venus; Pământ - Pluto; Pluto - Mercur; Mercur - Viena; Uranus - Neptun; Neptun - Saturn; Saturn – Jupiter; Jupiter - Marte și Marte - Uranus. Este posibil să zbori cu rachete obișnuite de pe Pământ pe Marte?

Soluţie: Să desenăm o diagramă a stării: vom reprezenta planetele ca puncte, iar rutele rachetei ca linii.

Acum este imediat clar că este imposibil să zbori de pe Pământ pe Marte.

Sarcina 2. Tabla are forma unei cruci duble, care se obține prin îndepărtarea pătratelor de colț dintr-un pătrat de 4x4.

Este posibil să o ocoliți mutând un cavaler de șah și revenind la pătratul original, după ce ați vizitat toate pătratele exact o dată?

Soluţie: Să numerotăm pătratele tablei succesiv:

Și acum, folosind figura, vom arăta că o astfel de parcurgere a tabelului, așa cum este indicată în condiție, este posibilă:

Am luat în considerare două probleme diferite. Cu toate acestea, soluțiile la aceste două probleme sunt unite printr-o idee comună - o reprezentare grafică a soluției. În același timp, imaginile desenate pentru fiecare sarcină s-au dovedit a fi similare: fiecare imagine este formată din mai multe puncte, dintre care unele sunt conectate prin linii.

Se numesc astfel de imagini grafice. Punctele sunt numite culmi, iar liniile - coaste grafic. Rețineți că nu orice imagine de acest tip va fi numită grafic. De exemplu. dacă vi se cere să desenați un pentagon în caiet, atunci un astfel de desen nu va fi un grafic. Vom numi un desen de acest tip, ca și în problemele anterioare, un grafic dacă există o sarcină specifică pentru care a fost construit un astfel de desen.

O altă notă se referă la aspectul graficului. Încercați să verificați dacă graficul pentru aceeași problemă poate fi desenat în moduri diferite; și invers, pentru sarcini diferite puteți desena grafice cu același aspect. Tot ce contează aici este ce vârfuri sunt conectate între ele și care nu. De exemplu, graficul pentru sarcina 1 poate fi desenat diferit:

Se numesc astfel de grafice identice, dar desenate diferit izomorfă.

Gradele vârfurilor și numărarea numărului de muchii ale unui grafic

Să mai scriem o definiție: gradul unui vârf dintr-un grafic este numărul de muchii care ies din acesta. În acest sens, un vârf cu grad par se numește vârf par, respectiv, un vârf cu grad impar se numește vârf impar.

Una dintre principalele teoreme ale teoriei grafurilor este legată de conceptul de grad de vârf - teorema privind corectitudinea numărului de vârfuri impare. O vom demonstra puțin mai târziu, dar mai întâi, pentru ilustrare, vom lua în considerare problema.

Sarcina 3. Există 15 telefoane în orașul Malenky. Este posibil să le conectați cu fire, astfel încât fiecare telefon să fie conectat la exact alte cinci?

Soluţie: Să presupunem că o astfel de conexiune între telefoane este posibilă. Apoi imaginați-vă un grafic în care vârfurile reprezintă telefoanele, iar marginile reprezintă firele care le conectează. Să numărăm câte fire sunt în total. Fiecare telefon are exact 5 fire conectate, adică. gradul fiecărui vârf al graficului nostru este 5. Pentru a găsi numărul de fire, trebuie să însumați gradele tuturor vârfurilor graficului și să împărțiți rezultatul rezultat la 2 (deoarece fiecare fir are două capete, atunci când însumați gradele, fiecare fir va fi luat de 2 ori) . Dar atunci numărul de fire va fi diferit. Dar acest număr nu este un număr întreg. Aceasta înseamnă că presupunerea noastră că fiecare telefon poate fi conectat la exact cinci alte telefon s-a dovedit a fi incorectă.

Răspuns. Este imposibil să conectați telefoanele în acest fel.

Teorema: Orice grafic conține un număr par de vârfuri impare.

Dovada: Numărul de muchii ale unui grafic este egal cu jumătate din suma gradelor vârfurilor acestuia. Deoarece numărul de muchii trebuie să fie un întreg, suma gradelor vârfurilor trebuie să fie pară. Și acest lucru este posibil numai dacă graficul conține un număr par de vârfuri impare.

Conectivitate grafică

Există un alt concept important legat de grafice - conceptul de conectivitate.

Graficul este numit coerent, dacă oricare două dintre vârfurile sale pot fi conectate de, acestea. succesiune continuă de muchii. Există o serie de probleme a căror soluție se bazează pe conceptul de conectivitate grafică.

Sarcina 4. Există 15 orașe în țara lui Seven, fiecare oraș fiind legat prin drumuri de cel puțin alte șapte. Demonstrează că este la modă să ajungi din orice oraș în oricare altul.

Dovada: Luați în considerare două orașe arbitrare A și B și presupuneți că nu există nicio cale între ele. Fiecare dintre ele este conectat prin drumuri de cel puțin alte șapte și nu există niciun oraș care să fie legat de ambele orașe în cauză (altfel ar exista o cale de la A la B). Să desenăm o parte a graficului corespunzătoare acestor orașe:

Acum se vede clar că am primit cel puțin 16 orașe diferite, ceea ce contrazice condițiile problemei. Aceasta înseamnă că afirmația a fost dovedită prin contradicție.

Dacă luăm în considerare definiția anterioară, atunci enunțul problemei poate fi reformulat în alt mod: „Demonstrați că graficul rutier al țării Șapte este conectat”.

Acum știi cum arată un grafic conectat. Un graf deconectat are forma mai multor „piese”, fiecare fiind fie un vârf separat fără muchii, fie un graf conectat. Puteți vedea un exemplu de grafic deconectat în figură:

Fiecare astfel de piesă individuală este numită componenta conexă a graficului. Fiecare componentă conectată reprezintă un graf conectat și toate afirmațiile pe care le-am dovedit pentru grafurile conectate sunt valabile pentru acesta. Să ne uităm la un exemplu de problemă care utilizează o componentă conectată:

Problema 5. În Regatul Îndepărtat, există un singur tip de transport - un covor zburător. Există 21 de linii de covoare care pleacă din capitală, una din orașul Dalniy și 20 din toate celelalte orașe.Demonstrați că puteți zbura din capitală în orașul Dalniy.

Dovada: Este clar că dacă desenezi un grafic al covorului Regatului, acesta poate fi incoerent. Să ne uităm la componenta de conectivitate care include capitala Regatului. Sunt 21 de covoare care ies din capitală și 20 din orice alt oraș, cu excepția orașului Dalniy, prin urmare, pentru ca legea cu privire la un număr par de vârfuri impare să fie îndeplinită, este necesar ca orașul Dalniy să fie inclus. în aceeași componentă de conectivitate. Și deoarece componenta conectată este un graf conectat, atunci din capitală există o cale de-a lungul covoarelor până în orașul Dalniy, ceea ce trebuia demonstrat.

Grafice Euler

Probabil ați întâlnit sarcini în care trebuie să desenați o formă fără să ridicați creionul de pe hârtie și să desenați fiecare linie o singură dată. Se dovedește că o astfel de problemă nu este întotdeauna rezolvabilă, adică. Există figuri care nu pot fi desenate folosind această metodă. Problema solubilității unor astfel de probleme este inclusă și în teoria grafurilor. A fost explorat pentru prima dată în 1736 de marele matematician german Leonhard Euler, rezolvând problema podurilor Königsberg. Prin urmare, graficele care pot fi desenate în acest fel sunt numite grafice Euler.

Sarcina 6. Este posibil să desenați graficul prezentat în figură fără să ridicați creionul de pe hârtie și să desenați fiecare margine exact o dată?

Soluţie. Dacă desenăm graficul așa cum este menționat în condiție, atunci vom introduce fiecare vârf, cu excepția celui inițial și final, de același număr de ori în care ieșim din el. Adică, toate vârfurile graficului, cu excepția a două, trebuie să fie pare. Graficul nostru are trei vârfuri impare, deci nu poate fi desenat în modul specificat în condiție.

Acum am demonstrat teorema despre graficele lui Euler:

Teorema: Un graf Euler trebuie să aibă cel mult două vârfuri impare.

Și în concluzie - problema podurilor Königsberg.

Sarcina 7. Figura prezintă o diagramă a podurilor din orașul Königsberg.

Este posibil să faceți o plimbare astfel încât să traversați fiecare pod exact o dată?

3. Probleme pentru subiectul „Grafe”

Conceptul de grafic.

1. Pe o tablă pătrată de 3x3, 4 cavaleri sunt așezați așa cum se arată în Fig. 1. Este posibil, după ce au făcut mai multe mișcări cu cavalerii, să le rearanjați în poziția prezentată în Fig. 2?

Orez. 1

Orez. 2

Soluţie. Să numerotăm pătratele tablei așa cum se arată în figură:

Să atribuim un punct pe plan fiecărei celule și, dacă o celulă poate fi atinsă prin mutarea unui cavaler de șah dintr-o celulă, atunci vom conecta punctele corespunzătoare cu o linie. Amplasarea inițială și necesară a cavalerilor sunt prezentate în figuri:

Pentru orice secvență de mișcări ale cavalerului, ordinea lor evident nu se poate schimba. Prin urmare, este imposibil să rearanjați caii în modul necesar.

2. În țara Digit există 9 orașe cu nume 1, 2, 3, 4, 5, 6, 7, 8, 9. Un călător a descoperit că două orașe sunt conectate printr-o companie aeriană dacă și numai dacă cele două cifre număr format din denumirile orașe, împărțit la 3. Se poate zbura cu avionul din orașul 1 în orașul 9?

Soluţie. Atribuind un punct fiecărui oraș și conectând punctele cu o linie, dacă suma numerelor este divizibilă cu 3, obținem un grafic în care numerele 3, 5, 9 sunt legate între ele, dar nu sunt legate de odihnă. Aceasta înseamnă că nu puteți zbura din orașul 1 în orașul 9.

Gradele vârfurilor și numărarea numărului de muchii.

3. Există 100 de orașe într-un stat, iar fiecare oraș are 4 drumuri. Câte drumuri sunt în stat?

Soluţie. Să numărăm numărul total de drumuri care părăsesc orașul - 100 . 4 = 400. Cu toate acestea, cu acest calcul, fiecare drum este numărat de 2 ori - iese dintr-un oraș și intră în altul. Aceasta înseamnă că sunt de două ori mai puține drumuri în total, adică. 200.

4. În clasă sunt 30 de persoane. S-ar putea ca 9 persoane să aibă 3 prieteni, 11 să aibă 4 prieteni și 10 să aibă 5 prieteni?

Răspuns. Nu (teorema privind paritatea numărului de vârfuri impare).

5. Regele are 19 vasali. S-ar putea ca fiecare vasal să aibă 1, 5 sau 9 vecini?

Răspuns. Nu el nu poate.

6. Poate un stat în care exact 3 drumuri ies din fiecare oraș să aibă exact 100 de drumuri?

Soluţie. Să numărăm numărul de orașe. Numărul de drumuri este egal cu numărul de orașe x înmulțit cu 3 (numărul de drumuri care părăsesc fiecare oraș) și împărțit la 2 (vezi problema 3). Atunci 100 = 3x/2 => 3x = 200, ceea ce nu se poate întâmpla cu x natural. Aceasta înseamnă că nu pot exista 100 de drumuri într-o astfel de stare.

7. Demonstrați că numărul de oameni care au trăit vreodată pe Pământ și au făcut un număr impar de strângeri de mână este par.

Demonstrarea rezultă direct din teorema privind paritatea numărului de vârfuri impare dintr-un grafic.

Conectivitate.

8. La tara, 100 de drumuri pleaca din fiecare oras si din fiecare oras poti ajunge in oricare altul. Un drum a fost închis pentru reparații. Demonstrează că acum poți ajunge din orice oraș în oricare altul.

Dovada. Să luăm în considerare componenta de conectivitate, care include unul dintre orașe, drumul între care a fost închis. Prin teorema privind paritatea numărului de vârfuri impare, include și al doilea oraș. Aceasta înseamnă că puteți găsi în continuare o rută și puteți ajunge dintr-unul dintre aceste orașe în altul.

Grafice Euler.

9. Există un grup de insule legate prin poduri astfel încât din fiecare insulă să poţi ajunge pe oricare alta. Turistul s-a plimbat în jurul tuturor insulelor, traversând fiecare pod o dată. A vizitat Threefold Island de trei ori. Câte poduri duc de la Troyekratnoye dacă un turist

a) nu a început cu ea și nu s-a terminat cu ea?
b) a început cu ea, dar nu a terminat cu ea?
c) a început cu ea și a terminat cu ea?

10. Imaginea prezintă un parc împărțit în mai multe părți prin garduri. Este posibil să te plimbi prin parc și prin împrejurimi, astfel încât să poți cățăra fiecare gard o dată?

Graficele în informatică sunt o modalitate de definire a relațiilor într-o colecție de elemente. Acestea sunt principalele obiecte de studiu

Definiții de bază

În ce constă un grafic în informatică? Include multe obiecte numite vârfuri sau noduri, dintre care unele perechi sunt conectate prin așa-numitele. coaste. De exemplu, graficul din figura (a) constă din patru noduri, etichetate A, B, C și D, dintre care B este conectat la fiecare dintre celelalte trei vârfuri prin muchii, iar C și D sunt de asemenea conectate. Două noduri sunt adiacente dacă sunt conectate printr-o muchie. Figura arată un mod tipic de a construi grafice în informatică. Cercurile reprezintă vârfuri, iar liniile care leagă fiecare pereche sunt muchii.

Care grafic se numește nedirecționat în informatică? Relația sa între cele două capete ale muchiei este simetrică. Marginea pur și simplu le conectează între ele. În multe cazuri, totuși, este necesar să se exprime relații asimetrice - de exemplu, că A indică către B, dar nu invers. Acest scop este servit de definiția informatică a unui graf, constând încă dintr-un set de noduri împreună cu un set de muchii direcționate. Fiecare muchie direcționată reprezintă o legătură între vârfuri, a cărei direcție contează. Graficele direcționate sunt reprezentate așa cum se arată în figura (b), marginile lor sunt reprezentate de săgeți. Când este necesar să subliniem că un graf este nedirecționat, se numește nedirecționat.

Modele de rețea

Graficele în informatică servesc ca structuri de rețea. Următoarea figură arată structura Internetului, numit atunci ARPANET, în decembrie 1970, când avea doar 13 puncte. Nodurile reprezintă centre de calcul, iar muchiile conectează două vârfuri cu o legătură directă între ele. Ignorând suprapunerea hărții SUA, restul imaginii este un grafic cu 13 noduri similar cu cele precedente. În acest caz, locația reală a vârfurilor este lipsită de importanță. Este important ce noduri sunt conectate între ele.

Utilizarea graficelor în informatică ne permite să vizualizăm modul în care lucrurile sunt fie fizic, fie logic conectate între ele într-o structură de rețea. ARPANET cu 13 noduri este un exemplu de rețea de comunicații în care vârfurile, computerele sau alte dispozitive pot transmite mesaje, iar marginile reprezintă linii de comunicație directe de-a lungul cărora pot fi transferate informații.

Trasee

Deși graficele sunt folosite în multe domenii diferite, ele au caracteristici comune. Teoria graficelor (informatica) include, poate cea mai importantă dintre acestea, ideea că lucrurile se deplasează adesea de-a lungul marginilor, deplasându-se secvenţial de la un nod la altul, fie că este vorba despre un pasager pe mai multe zboruri, fie că este vorba de un pasager pe mai multe zboruri sau de informaţii transmise de la o persoană la alta pe o reţea socială. rețea, sau un utilizator un computer care vizitează secvenţial o serie de pagini web urmând link-uri.

Această idee motivează definirea unui traseu ca o secvență de vârfuri conectate prin muchii. Uneori devine necesar să se ia în considerare o rută care conține nu numai noduri, ci și o secvență de margini care le conectează. De exemplu, succesiunea de vârfuri MIT, BBN, RAND, UCLA este o rută în graficul Internet ARPANET. Trecerea nodurilor și marginilor se poate repeta. De exemplu, SRI, STAN, UCLA, SRI, UTAH, MIT este, de asemenea, o rută. O cale în care marginile nu se repetă se numește circuit. Dacă nodurile nu se repetă, atunci se numește lanț simplu.

Cicluri

Tipuri deosebit de importante de grafice în informatică sunt buclele, care sunt o structură inelă, cum ar fi o secvență de noduri LINC, CASE, CARN, HARV, BBN, MIT, LINC. Rutele cu cel puțin trei margini, unde primul și ultimul nod sunt același și restul sunt diferite, sunt grafice ciclice în informatică.

SRI, STAN, UCLA, SRI este cel mai scurt, iar SRI, STAN, UCLA, RAND, BBN, UTAH, SRI este semnificativ mai lung.

De fapt, fiecare margine a graficului ARPANET aparține unui ciclu. Acest lucru a fost făcut în mod intenționat: dacă vreuna dintre ele eșuează, va fi în continuare posibilă trecerea de la un nod la altul. Buclele în sistemele de comunicații și transport sunt prezente pentru a oferi redundanță - ele oferă rute alternative de-a lungul unei căi de buclă diferită. Ciclurile sunt adesea vizibile și în rețeaua de socializare. Când descoperi, de exemplu, că prietenul apropiat de școală al vărului soției tale chiar lucrează cu fratele tău, atunci este un ciclu care constă din tine, soția ta, vărul ei, prietenul lui de școală, angajatul lui (adică, fratele tău) și în cele din urmă tu din nou.

Grafic conectat: definiție (informatică)

Este firesc să ne întrebăm dacă este posibil să ajungi de la fiecare nod la orice alt nod. Un grafic este conectat dacă există o rută între fiecare pereche de vârfuri. De exemplu, rețeaua ARPANET este un graf conectat. Același lucru se poate spune și pentru majoritatea rețelelor de comunicații și transport, deoarece scopul lor este de a direcționa traficul de la un nod la altul.

Pe de altă parte, nu există niciun motiv a priori să ne așteptăm că aceste tipuri de grafice sunt larg răspândite în informatică. De exemplu, pe o rețea de socializare este ușor să ne imaginăm doi oameni care nu sunt conectați unul la altul.

Componente

Dacă graficele din informatică nu sunt conectate, atunci ele se încadrează în mod natural într-un set de fragmente conectate, grupuri de noduri care sunt izolate și disjunse. De exemplu, figura prezintă trei astfel de părți: prima este A și B, a doua este C, D și E, iar a treia este formată din vârfurile rămase.

Componentele conexe ale unui graf sunt un subset de noduri care:

• fiecare vârf al subgrupului are o rută către oricare altul;
• un subset nu face parte dintr-un set mai mare în care fiecare nod are o rută către fiecare celălalt.

Când graficele din informatică sunt împărțite în componentele lor, acesta este doar un mod de început de a descrie structura lor. În cadrul unei anumite componente poate exista o structură internă bogată care este importantă pentru interpretarea rețelei. De exemplu, o metodă formală pentru a determina importanța unui nod este de a determina în câte părți s-ar împărți graficul dacă nodul ar fi eliminat.

Componenta maxima

Există o metodă de evaluare calitativă a componentelor de conectivitate. De exemplu, există o rețea socială la nivel mondial cu conexiuni între două persoane dacă sunt prieteni.

Este ea conectată? Probabil ca nu. Conectivitatea este o proprietate destul de fragilă, iar comportamentul unui nod (sau a unui set mic al acestora) o poate anula. De exemplu, o singură persoană fără prieteni vii ar fi o singură componentă de vârf și, prin urmare, graficul nu ar fi conectat. Sau o insulă tropicală îndepărtată, formată din oameni care nu au contact cu lumea exterioară, ar fi, de asemenea, o mică componentă a rețelei, confirmând deconectarea acesteia.

Rețea globală de prieteni

Dar mai e ceva. De exemplu, un cititor al unei cărți populare are prieteni care au crescut în alte țări și este una cu ei. Dacă luăm în calcul părinții acestor prieteni și prietenii lor, atunci toți acești oameni sunt și ei în aceeași componentă, deși nu au auzit niciodată de cititor, vorbesc o altă limbă și nu au fost niciodată lângă el. Astfel, deși rețeaua globală de prietenie nu este coerentă, cititorul va intra într-o componentă de dimensiuni foarte mari, care pătrunde în toate părțile lumii, inclusiv în oameni din toate categoriile sociale și, de fapt, conținând o parte semnificativă. a populației lumii.

Același lucru este valabil și în seturile de date de rețea - rețelele mari și complexe au adesea o componentă maximă care include o parte semnificativă a tuturor nodurilor. Mai mult, atunci când o rețea conține o componentă maximă, aproape întotdeauna există doar una. Pentru a înțelege de ce, trebuie să ne întoarcem la exemplul rețelei globale de prietenie și să încercăm să ne imaginăm că avem două componente maxime, fiecare conținând milioane de oameni. Ar fi necesar să existe o singură margine de la cineva de la prima componentă la a doua pentru ca cele două componente maxime să se îmbine într-una singură. Deoarece există o singură margine, în majoritatea cazurilor este imposibil să nu se formeze și, prin urmare, două componente maxime nu sunt niciodată observate în rețelele reale.

În unele cazuri rare în care două componente maxime au coexistat mult timp într-o rețea reală, fuziunea lor a fost neașteptată, dramatică și în cele din urmă dezastruoasă.

Dezastru de îmbinare a componentelor

De exemplu, după sosirea exploratorilor europeni în civilizațiile din emisfera vestică în urmă cu aproximativ o jumătate de mileniu, a avut loc un cataclism global. Din perspectiva rețelei, arăta astfel: Timp de cinci mii de ani, rețeaua socială globală a constat probabil din două componente uriașe - una în Americi, cealaltă în Eurasia. Din acest motiv, tehnologia s-a dezvoltat independent în cele două componente și, și mai rău, la fel și bolile umane etc. Când cele două componente au intrat în sfârșit în contact, tehnologiile și bolile uneia l-au copleșit rapid și catastrofal pe cealaltă.

liceul american

Conceptul de componente maxime este util pentru a ne gândi la rețele la o scară mult mai mică. Un exemplu interesant este un grafic care ilustrează relațiile romantice într-un liceu american pe o perioadă de 18 luni. Faptul că conține componenta maximă este important atunci când vine vorba de răspândirea bolilor cu transmitere sexuală, care a fost și scopul studiului. Este posibil ca studenții să fi avut un singur partener în această perioadă, dar au fost totuși, fără să-și dea seama, parte din componenta maximă și, prin urmare, parte a multor căi de transmisie potențială. Aceste structuri reflectă relații care s-ar putea să se fi încheiat cu mult timp în urmă, dar leagă indivizii în lanțuri prea mult timp pentru a fi subiectul controlului și bârfei. Cu toate acestea, ele sunt reale: ca fapte sociale, sunt macrostructuri invizibile, dar logice, care au apărut ca produs al medierii individuale.

Distanța și lățimea prima căutare

Pe lângă faptul că știm dacă două noduri sunt conectate printr-o rută, teoria grafurilor în informatică ne permite să aflăm despre lungimea sa - în transport, comunicații sau în răspândirea știrilor și a bolilor și dacă trece prin câteva vârfuri sau multe.

Pentru a face acest lucru, trebuie să determinați lungimea traseului egală cu numărul de pași pe care îi conține de la început până la sfârșit, adică numărul de margini din secvența care o alcătuiește. De exemplu, calea MIT, BBN, RAND, UCLA are o lungime de 3, iar MIT, UTAH are o lungime de 1. Folosind lungimea căii, putem vorbi despre dacă două noduri din grafic sunt situate aproape unul de celălalt sau departe: distanța dintre două vârfuri este definită ca lungimea drumului cel mai scurt dintre ele. De exemplu, distanța dintre LINC și SRI este de 3, deși pentru a fi sigur de acest lucru ar trebui să vă asigurați că nu există o lungime de 1 sau 2 între ele.

Algoritmul de căutare latimea întâi

Pentru graficele mici, distanța dintre două noduri este ușor de calculat. Dar pentru cele complexe, este nevoie de o metodă sistematică pentru determinarea distanțelor.

Cel mai natural mod de a face acest lucru și, prin urmare, cel mai eficient, este următorul (folosind exemplul unei rețele globale de prieteni):

• Toți prietenii sunt declarați a fi la o distanță de 1.
• Toți prietenii prietenilor (fără a număra cei deja marcați) sunt declarați a fi la o distanță de 2.
• Toți prietenii lor (din nou, fără a număra persoanele etichetate) sunt declarați la distanță de 3.

Continuând în acest fel, căutarea se efectuează în straturi ulterioare, fiecare dintre ele fiind cu o unitate mai departe decât precedentul. Fiecare strat nou este compus din noduri care nu au participat încă la cele anterioare și care sunt incluse în marginea cu vârful stratului anterior.

Această tehnică se numește căutare pe lățime, deoarece caută graficul spre exterior de la nodul de pornire, verificându-le mai întâi pe cele mai apropiate. Pe lângă faptul că oferă o modalitate de a determina distanța, poate servi ca un cadru conceptual util pentru organizarea structurii graficului, precum și modul de construire a unui grafic informatic prin aranjarea vârfurilor pe baza distanței lor de la un punct de plecare fix.

Căutarea pe lățime poate fi aplicată nu numai unei rețele de prieteni, ci și oricărui grafic.

E o lume mică

Dacă revenim la rețeaua globală de prieteni, putem observa că argumentul pentru apartenența la componenta maximă afirmă de fapt ceva mai mult: nu numai că cititorul are rute către prieteni care îl leagă de o proporție semnificativă a populației lumii, ci și acestea. rutele sunt surprinzător de scurte.

Această idee se numește „fenomenul lumii mici”: lumea pare mică dacă te gândești la cel mai scurt traseu care leagă oricare doi oameni.

Teoria „șase strângeri de mână” a fost studiată pentru prima dată experimental de Stanley Milgram și colegii săi în anii 1960. Fără niciun set de date de rețele sociale și un buget de 680 de dolari, el a decis să testeze o idee populară. În acest scop, el a cerut 296 de inițiatori aleși la întâmplare să încerce să trimită o scrisoare unui agent de bursă care locuia într-o suburbie din Boston. Inițiatorilor li s-au oferit câteva informații personale despre țintă (inclusiv adresa și profesia) și li s-a cerut să transmită scrisoarea unei persoane pe care o cunoșteau pe nume cu aceleași instrucțiuni pentru ca aceasta să ajungă la țintă cât mai repede posibil. Fiecare scrisoare a trecut prin mâinile unui număr de prieteni și a format un lanț care s-a încheiat cu un agent de bursă în afara Bostonului.

Dintre cele 64 de lanțuri care au atins obiectivul, lungimea medie a fost de șase, confirmând numărul dat cu două decenii mai devreme în titlul piesei lui John Gair.

În ciuda tuturor neajunsurilor acestui studiu, experimentul a demonstrat unul dintre cele mai importante aspecte ale înțelegerii noastre despre rețelele sociale. În anii următori, s-a tras o concluzie mai amplă: rețelele sociale tind să aibă căi foarte scurte între perechi arbitrare de oameni. Și chiar dacă astfel de legături indirecte cu directori de afaceri și lideri politici nu dau roade zilnic, existența unor astfel de rute scurte joacă un rol important în viteza cu care informațiile, bolile și alte tipuri de contagiune se răspândesc în societate, precum și ca și în oportunitățile de acces pe care o rețea de socializare le oferă persoanelor cu calități complet opuse.

Informații teoretice

Rețineți că în problemele de construcție soluția trebuie căutată printre grafice simple nedirecționate (adică, grafice fără margini multiple și fără bucle). Din păcate, nu există o tehnică universală care să vă permită să determinați cu precizie dacă poate fi construit un grafic cu caracteristici date.

Este important să ne amintim că, în orice grafic, suma gradelor tuturor vârfurilor sale este un număr par, egal cu dublul numărului de muchii ale graficului, deoarece fiecare muchie participă la această sumă exact de două ori. Acest rezultat, cunoscut lui Euler acum 200 de ani, este adesea numit lema strângerii de mână. Rezultă din aceasta că, dacă mai multe persoane dau mâna, atunci numărul total de strângeri de mână este în mod necesar par, deoarece în fiecare strângere de mână sunt implicate două mâini (fiecare mână este numărată de câte ori a participat la strângeri de mână). Rezultă că:

• numărul de vârfuri cu grade impare în orice grafic este par;
• în orice grafic cu P culmi unde P> 2, există întotdeauna cel puțin două vârfuri cu aceleași grade;
• dacă într-un grafic cu vârfuri p> 2 exact două vârfuri au același grad, atunci în acest grafic există întotdeauna fie exact un vârf de grad 0, fie exact un vârf de grad (P - 1).

Când rezolvați probleme, trebuie să citiți condițiile cu mare atenție, deoarece multe adjective care descriu proprietățile unui grafic au echivalente numerice. Prezentăm un tabel cu astfel de corespondențe care se găsesc cel mai des în formularea problemelor (Tabelul 2.9).

După ce ați obținut toate numerele necesare, trebuie să încercați să calculați caracteristicile lipsă ale graficului. Uneori, condiția dă gradele tuturor sau mai multor vârfuri. În acest caz, pe baza faptului că fiecare muchie a graficului adaugă exact două vârfuri la gradul său total, putem folosi formula

X5 (y/) =2t'

Unde T - număr de vârfuri, iar însumarea se efectuează pe toate vârfurile de la 1 la P.

Sarcini

Problema 2.42. Construiți un grafic pe opt vârfuri care are următoarea distribuție a gradelor de vârf: două vârfuri de gradul 4; trei vârfuri de gradul 3; două vârfuri de gradul 2; un vârf de gradul 1.

Soluţie.

Gradul total al tuturor vârfurilor este 2-4 + 3- 3 + 2- 2+1 1=22, ceea ce înseamnă că există 11 muchii în total. Este mai ușor să construiești grafice pe baza unui vector de grade, pornind de la vârfuri de grade mari. Ver-

Tabelul 2.9

Corespondența dintre descrierea unui grafic și proprietățile acestuia

Adjectiv	Numeral	Ce înseamnă
		Graficul are exact o componentă conectată
Incoerent		Graficul are mai mult de o componentă, diametrul său este exact egal cu infinitul
Regulat	5(U;) = SOSHI	Gradele tuturor vârfurilor sunt egale
Grad obișnuit	з(Уі)=У	Gradele tuturor vârfurilor sunt egale u. Daca este cunoscut P(număr de vârfuri), apoi puteți calcula imediat T(numar de coaste): da-p? y/2 (P sau la trebuie să fie un număr par)
Aciclic	y= t-p + k = 0	Numărul ciclomatic este zero, graficul nu are cicluri, este un copac sau o pădure (în funcție de conectivitate), astfel de grafice pot fi întotdeauna colorate în două culori. Dacă două din trei variabile sunt cunoscute ( P, t, k), apoi folosind formula puteți găsi restul
Arborele (sau graficul conectat aciclic)	y=t-n+ 1 =0, de unde T- n - 1	Numărul ciclomatic este zero, graficul nu are cicluri, este un arbore, astfel de grafice pot fi întotdeauna colorate în două culori. Dacă una dintre cele două variabile este cunoscută ( P sau T), apoi folosind formula puteți găsi a doua
Bicromatic		Numărul cromatic al unui grafic este doi, astfel de grafice pot fi întotdeauna colorate în două culori, acestea sunt grafice bipartite, grafic sunt fie grafice aciclice, fie grafice în care toate ciclurile au o lungime egală.

Este mai bine să aranjați magistralele în reprezentarea grafică a graficului astfel încât să se intersecteze cât mai puține muchii și arce, iar vârfurile în sine să fie grupate după un criteriu de similitudine. Una dintre opțiuni este prezentată în Fig. 2.8.

Problema 2.43. Construiți un grafic pe șase vârfuri care să aibă următoarea distribuție a gradelor de vârf: două vârfuri de gradul 3;

Orez. 2.8.

două vârfuri de gradul 2; un vârf de gradul 1; un vârf are un grad arbitrar.

Soluţie.

Gradul total al vârfurilor este 11, prin urmare, vârful rămas trebuie să aibă un grad impar, adică. 1,3 sau 5. Astfel, se pot construi trei grafice diferite (Fig. 2.9).

Orez. 2.9.

Problema 2.44. Construiți un grafic cu următorul vector de grade vârfuri: 5 = (1, 2, 2, 3, 4, 4, 5).

Soluţie.

Gradul total este 5 + 8 + 3 + 4+1=21. Deoarece acesta este un număr impar, ceea ce contrazice teorema (numărul de muchii este jumătate din acest număr, dar 21 nu este divizibil egal cu 2).

Răspuns. Nu există un astfel de grafic.

Problema 2.45. Construiți un grafic cu următorul vector de grade vârfuri: 5 = (1, 1,2, 2, 2, 4, 4, 4, 4).

Problema 2.46. Construiți un grafic cu următorul vector de grade vârfuri: 5 = (5, 5, 6, 6, 6, 6, 6).

Problema 2.47. Construiți un grafic cu următorul vector de grade vârfuri: 5 = (1, 1, 1,2, 3, 3, 3, 3, 5, 5, 5).

Problema 2.48. Construiți un grafic cu următorul vector de grade vârfuri: 5 = (3, 3, 3, 3, 3, 3, 3, 7).

Problema 2.49. Construiți un grafic pe șase vârfuri care să aibă următoarea distribuție a gradelor de vârf: trei vârfuri sunt de gradul 5, iar celelalte trei vârfuri sunt de grad necunoscut.

Problema 2.50. Construiți un grafic pe zece vârfuri, cu de două ori mai multe muchii decât vârfuri și următoarea distribuție a gradelor de vârf: două vârfuri de gradul 6; patru vârfuri de gradul 5; două vârfuri de gradul 4; două vârfuri de grad arbitrar – sau justifică imposibilitatea construirii unui astfel de graf.

Problema 2.51. Construiți un grafic pe zece vârfuri care are următoarea distribuție a gradelor de vârf: un vârf de gradul 7; două vârfuri de gradul 6; două vârfuri de gradul 5; două vârfuri de gradul 4; două vârfuri de gradul 3; un vârf de gradul 2 - sau justifica imposibilitatea construirii unui astfel de grafic.

Problema 2.52. Construiți un grafic pe 11 vârfuri care să aibă următoarea distribuție a gradelor de vârf: un vârf de gradul 7; două vârfuri de gradul 6; două vârfuri de gradul 5; două vârfuri de gradul 4; două vârfuri de gradul 3; un vârf de gradul 2 - sau justifica imposibilitatea construirii unui astfel de grafic.

Graficul nul și graficul complet.

Există unele grafice speciale care apar în multe aplicații ale teoriei grafurilor. Pentru moment, vom considera din nou graficul ca o diagramă vizuală care ilustrează cursul competițiilor sportive. Înainte de începerea sezonului, deși nu s-au jucat încă jocuri, nu există margini în grafic. Un astfel de grafic constă numai din vârfuri izolate, adică. de vârfuri conectate fără muchii. Vom numi un grafic de acest tip grafic nul. În fig. 3 prezintă astfel de grafice pentru cazurile în care numărul de comenzi, sau vârfuri, este 1, 2, 3, 4 și 5. Aceste grafice nule sunt de obicei notate cu simbolurile O1, O2, O3 etc., deci On este un a nul. grafic cu n vârfuri și fără muchii.

Să luăm în considerare un alt caz extrem. Să presupunem că la sfârșitul sezonului, fiecare echipă joacă un meci împotriva fiecăreia dintre celelalte echipe. Apoi, pe graficul corespunzător, fiecare pereche de vârfuri va fi conectată printr-o muchie. Un astfel de grafic se numește grafic complet. Figura 4 prezintă grafice complete cu numărul de vârfuri n = 1, 2, 3, 4, 5. Notăm aceste grafice complete cu U1, U2, U3, U4 și respectiv U5, astfel încât graficul Un este format din 11 vârfuri și muchii, conectând toate perechile posibile ale acestor vârfuri. Acest grafic poate fi considerat ca un n-gon în care sunt desenate toate diagonalele.

Având un grafic, de exemplu graficul G prezentat în Fig. 1, îl putem transforma oricând într-un grafic complet cu aceleași vârfuri adăugând muchiile lipsă (adică muchiile corespunzătoare jocurilor care nu au fost încă jucate). În fig. 5 am făcut acest lucru pentru graficul din Fig. 1 (jocurile care nu au avut loc încă sunt afișate în linii punctate). De asemenea, puteți desena separat un grafic corespunzător jocurilor viitoare care nu au fost încă jucate. Pentru graficul G, aceasta va avea ca rezultat graficul prezentat în Fig. 6.

Numim acest nou graf complementul grafului G; Se obișnuiește să-l notăm cu G1. Luând complementul graficului G1, obținem din nou graficul G. Muchiile ambelor grafice G1 și G formează împreună un grafic complet.

1736, Koenigsberg. Râul Pregelya curge prin oraș. Există șapte poduri în oraș, situate așa cum se arată în figura de mai sus. Din cele mai vechi timpuri, locuitorii din Königsberg s-au luptat cu o ghicitoare: este posibil să traversezi toate podurile, mergând pe fiecare o singură dată? Această problemă a fost rezolvată atât teoretic, pe hârtie, cât și în practică, pe plimbări - trecând chiar de-a lungul acestor poduri. Nimeni nu a putut dovedi că acest lucru este imposibil, dar nimeni nu a putut face o plimbare atât de „misterioasă” peste poduri.

Celebrul matematician Leonhard Euler a reușit să rezolve problema. Mai mult, a rezolvat nu numai această problemă specifică, ci a venit cu o metodă generală de rezolvare a unor probleme similare. Când a rezolvat problema podurilor Königsberg, Euler a procedat după cum urmează: a „comprimat” pământul în puncte și a „întins” podurile în linii. O astfel de figură, constând din puncte și linii care leagă aceste puncte, se numește NUMARA.

Un grafic este o colecție de un set nevid de vârfuri și conexiuni între vârfuri. Cercurile sunt numite vârfuri ale graficului, liniile cu săgeți sunt arce, iar liniile fără săgeți sunt muchii.

Tipuri de grafice:

1. Graficul dirijat(scurt digraf) - cărora li se atribuie muchii o direcție.

2. Grafic nedirecționat este un grafic în care nu există direcția liniilor.

3. Grafic ponderat– arcele sau muchiile au greutate (informații suplimentare).

Rezolvarea problemelor folosind grafice:

Sarcina 1.

Soluție: Să notăm oamenii de știință ca vârfuri ale graficului și să desenăm linii de la fiecare vârf la alte patru vârfuri. Obținem 10 rânduri, care vor fi considerate strângeri de mână.

Sarcina 2.

Pe terenul școlii cresc 8 copaci: măr, plop, mesteacăn, rowan, stejar, arțar, zada și pin. Rowan este mai înalt decât zada, mărul este mai înalt decât artarul, stejarul este mai jos decât mesteacănul, dar mai înalt decât pinul, pinul este mai mare decât șorbalul, mesteacănul este mai jos decât plopul și zada este mai mare decât mărul. Aranjați copacii de la cel mai scurt la cel mai înalt.

Soluţie:

Vârfurile graficului sunt arbori, indicați prin prima literă a numelui arborelui. Există două relații în această sarcină: „a fi mai jos” și „a fi mai sus”. Luați în considerare relația „a fi mai jos” și trageți săgeți dintr-un copac inferior într-unul superior. Daca problema spune ca frasinul de munte este mai inalt decat zada, atunci punem o sageata de la zada la frasinul de munte etc. Obținem un grafic care arată că cel mai scurt copac este arțarul, urmat de măr, zada, rowan, pin, stejar, mesteacăn și plop.

Sarcina 3.

Natasha are 2 plicuri: obișnuit și aer, și 3 ștampile: dreptunghiular, pătrat și triunghiular. În câte moduri poate Natasha să aleagă un plic și o ștampilă pentru a trimite o scrisoare?

Soluţie:

Mai jos este o defalcare a sarcinilor.