Grafer over veinett og algoritmer for å jobbe med dem. Matematisk modell

Uttalelse. Hvis det for to toppunkter er en rute som forbinder dem, så er det garantert en minimal rute som forbinder disse toppunktene. La oss betegne lengden på denne ruten medd(v,w).

Definisjon. Størrelsed(v,w) (endelig eller uendelig) vil bli kalt avstand mellom toppunktene v, w . Denne avstanden tilfredsstiller de metriske aksiomene:

1) d(v,w) 0, ogd(v,w) = 0 hvis og bare hvisv=w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

Definisjon. Diameter av en tilkoblet graf er den maksimalt mulige avstanden mellom to av dens toppunkter.

Definisjon. Senter en graf kalles et toppunkt slik at maksimal avstand mellom den og et hvilket som helst annet toppunkt er det minste av alle mulige; denne avstanden kalles radius kurve.

Eksempel 82.

For grafen G vist i fig. 3.16, finn radius, diameter og sentra.

Ris. 3.16. Graf for eksempel 82

Løsning.

For å bestemme sentre, radius, diameter på grafen G, la oss finne matrisen D(G) avstander mellom grafens toppunkter, elementer d ij som vil være avstandene mellom toppunktene v i Og v j. Til dette vil vi bruke grafisk representasjon kurve. Merk at matrisen D(G) symmetrisk om hoveddiagonalen.

Bruke den resulterende matrisen for hvert toppunkt i grafen G La oss bestemme den største fjerningen fra uttrykket: Til jeg,j = 1, 2, …, 5. Som et resultat får vi: r(v 1) = 3,r(v 2) = 2,r(v 3) = 2,r(v 4) = 2,r(v 5) = 3. Minimum av de resulterende tallene er radiusen til grafen G, maksimal – grafdiameter G. Betyr, R(G) = 2 Og D(G) = 3, sentrene er toppunktene v2,v 3,v 4.

Å beregne avstander og bestemme ruter i en graf er et av de mest åpenbare og praktiske problemene som oppstår i grafteori. La oss introdusere noen nødvendige definisjoner.

Eksentrisitet grafisk toppunkt – avstanden til det maksimale toppunktet fra den. For en graf som den ikke er definert for vekt dens kanter, er avstanden definert som antall kanter.

Radius grafen er minimum eksentrisitet av toppunktene, og diameter graf – maksimal eksentrisitet av toppunkter.

Senter grafen er dannet av toppunkter hvis eksentrisitet lik radius. Sentrum av grafen kan bestå av ett, flere eller alle toppunktene i grafen.

Perifer toppunktene har en eksentrisitet lik diameteren.

En enkel kjede med lengde lik diameteren på grafen kalles diametral .

Teorem 12.1.I en tilkoblet graf er ikke diameteren større enn rangeringen av dens tilstøtende matrise.

Teorem 12.2.(Jordan) Hvert tre har et senter som består av ett eller to tilstøtende hjørner.

Teorem 12.3.Hvis diameteren på treet er jevn, har treet et enkelt senter, og alle diametralske kjeder passerer gjennom det hvis diameteren er oddetall, så er det to sentre og alle diametralske kjeder inneholder en kant som forbinder dem.

Åpenbart praktisk betydning midten av grafen. Hvis f.eks. vi snakker om om en graf over veier med bypunktpunkt, så er det tilrådelig å plassere i det matematiske sentrum administrativt senter, varehus osv. Den samme tilnærmingen kan brukes på en vektet graf, der avstandene er vektene til kantene. Som vekt kan du ta den euklidiske avstanden, tiden eller kostnadene ved bevegelse mellom punktene.

Eksempel 12.5. Finn radius, diameter og sentrum av grafen vist i fig. 12.1.

Løsning. I denne oppgaven er det praktisk å bruke avstandsmatrise S. Element av denne kvadratsymmetriske matrisen lik avstanden mellom toppen jeg og toppen j. For grafen vist i fig. 12.1, har avstandsmatrisen neste visning:

La oss beregne eksentrisiteten til hvert toppunkt. Denne verdien kan defineres som det maksimale elementet i den tilsvarende kolonnen i avstandsmatrisen (eller raden - siden matrisen S symmetrisk). Vi får

Grafradius r– minimum eksentrisitet av toppunktene. I i dette tilfellet r= 2. Toppene nr. 2, nr. 4 og nr. 5 har en slik eksentrisitet. Tell diameter d– maksimal eksentrisitet av toppunktene. I dette tilfellet d= 3. Topper nr. 1 og nr. 3 har slik eksentrisitet dette er periferien av grafen. I den studerte grafen viste toppunktene seg å være enten sentrale eller perifere. I grafer av høyere orden er det andre toppunkter.

Eksentrisitetene til toppunktene til en liten graf kan enkelt beregnes ved direkte beregning fra tegningen. Imidlertid er grafen ikke alltid definert av utformingen. I tillegg kan grafen ha stor størrelse. Derfor er det nødvendig med en annen måte å løse det forrige problemet på. Følgende teorem er kjent.

Teorem 12.4. La være tilstøtende matrisen til en graf G uten løkker og , Hvor . Da lik antall ruter med lengde k fra toppunkt til toppunkt.

Å løse grafteoretiske problemer ved å bruke ulike transformasjoner av tilstøtende matrisen kalles algebraisk metode .

Eksempel 12.6. Finn avstandsmatrisen til grafen vist i fig. 12.1, ved å bruke den algebraiske metoden.

Løsning. Nærhetsmatrisen til denne grafen er lik:

Vi vil fylle ut avstandsmatrisen ved å vurdere gradene til tilstøtningsmatrisen. Enhetene til tilstøtende matrisen viser par av hjørner som har en avstand på én mellom seg (det vil si at de er forbundet med en enkelt kant).

De diagonale elementene i avstandsmatrisen er null. Multipliser tilstøtende matrisen med seg selv:

I følge teoremet, mellom hjørnene 2 og 3, 1 og 4 osv. det er et visst antall ruter med lengde 2 (siden graden av matrisen er to). Antall ruter er ikke brukt her selve det faktum at en rute er tilstede og dens lengde er viktig, som indikert av ikke-null-elementet i matrisegraden, som ikke sammenfaller med elementet som er notert ved beregning av en rute av; kortere lengde. Vi legger 2 i de tomme elementene i avstandsmatrisen og får neste tilnærming:

Avstanden mellom hjørnene 1 og 3 forblir ukjent. Vi vil multiplisere tilstøtende matrisen på seg selv til i matrisen ikke-null element vil ikke vises . Deretter det tilsvarende elementet i avstandsmatrisen lik kraften tilstøtende matriser: . På neste trinn får vi

derfor, , og til slutt

Den resulterende matrisen faller sammen med avstandsmatrisen S(12.2), funnet ved direkte beregninger fra figuren.

La G(V,X) være en pseudograf og la toppunktene v og w (v¹w) i denne grafen være forbundet med en rute. Da må det være en minimal rute som forbinder disse toppunktene. La oss betegne lengden på denne ruten som d(v, w). Vi setter også d(v, v) =0 for et hvilket som helst toppunkt vÎV; d(v, w) = ¥ hvis det ikke er noen rute som forbinder v og w.

Verdien d(v,w) definert på denne måten for eventuelle toppunkter v og w i grafen G(V, X) kalles avstanden mellom v og w.

Antall avstander i en graf med n toppunkter er lik antall kombinasjoner C n 2 .

La grafen G(V,X) kobles sammen. La oss definere følgende konsepter for det:

Tell diameter: d(G) = maksd(v, w).

Eksentrisitet (maksimal offset) av toppunktet: r(v) = maksd(v, w);

Grafradius: r(G) = min r(v);

Grafsenter: ethvert toppunkt vÎV slik at r(v) = r(G).

Diameteren til grafen, eksentrisitetene til toppunktene, radiusen til grafen og sentrene til grafen kalles de metriske egenskapene til grafen.

Eksempel. Finne metriske spesifikasjoner graf spesifisert av diagrammet:

La oss finne alle avstandene, med tanke på at d(v, w) = d(w, v).

Antall avstander i denne grafen C 5 2 = 5!/3!2! = 10: d(v 1, v 2) = 1, d(v 1, v 3) = 2, d(v 1, v 4) = 2, d(v 1, v 5) = 3, d(v 2, v 3) = 1, d(v 2, v 4) = 1, d(v 2, v 5) = 2, d(v 3, v 4) = 1, d(v 3, v 5) = 2, d(v 4, v 5) = 1.

Diameter på grafen d(G) =3.

Toppunkteksentrisiteter: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Grafradius r(G) = 2.

Sentrum av grafen er v 2, v 3, v 4.

3. Minimumsruter i innlastede grafer

En graf G(V, X) kalles lastet hvis en funksjon kalt en vektfunksjon er spesifisert på settet med kanter på grafen, som tildeler hver kant x ОХ av grafen et visst tall l(x). Verdien l(x) kalles buelengden.

Verdien l(x) kan gis annen betydning: transportkostnader, reisetid, avstand mellom punktene, bensinforbruk, etc.

Summen av lengdene på kantene som inngår i en rute kalles rutelengden.

Merk at hvis for alle x О Х l(x) = 1, så kan grafen betraktes som ubelastet.

En rute i grafen G(V, X) fra toppunkt v til toppunkt w (v¹w) kalles minimal hvis den har minimumslengden blant alle rutene i grafen G(V, X) fra toppunkt v til toppunkt w.

La oss begrense oss til grafer der l(x)>0.

Når du søker etter minimumsruten i en innlastet graf med l(x)>0

La oss bruke samme setning som for den ubelastede grafen, nemlig:

enhver minimal rute er en enkel krets.

La oss nå vurdere problemet med å finne minimumsruten i en lastet graf.

La grafen G(V,X) lastes, antall toppunkter n ³ 2, det er nødvendig å konstruere en minimal rute fra v 1 til v n .

La oss presentere algoritmen.

Trinn 1. Tilordne en indeks a(v i) til hvert toppunkt: a(v 1) = 0, a(v i) = ¥, i ¹ 1. Fargelegg toppunktet v 1 og sett v = v 1.

Trinn 2. For hvert ufarget toppunkt v j endre indeksen i henhold til regelen:

a(v j) = min (a(v j), a(v) + l(v, v j)).

Fargelegg toppunktet som a(v j) er minst for. Farg også kanten som fører til den valgte. dette trinnet toppunkt v j. Sett v = v j.

Trinn 3. Hvis v = v j, avslutt prosedyren, siden den korteste ruten er fra v 1 til v n. hvis v ¹ v n , gå til trinn 2.

Kommentar. Trinn 2 er umulig hvis alle a(v j)= ¥. I dette tilfellet er toppunktet v n utilgjengelig.

La oss bruke den beskrevne algoritmen på grafen spesifisert av diagrammet. La oss i den finne den korteste ruten fra v 1 til v 6.

Trinn 1. Farg toppunktet v 1 . La oss tilordne indekser til toppunktene: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Vi antar v 1 = v.

a(v 2) = min (¥, 0+4) = 4,

a(v 3) = min (¥, 0+7) = 7,

a(v 4) = min (¥, 0+3) = 3,

a(v 5) = min (¥, 0+¥) = ¥,

a(v 6) = min (¥, 0+¥) = ¥.

Farg toppunktet v 4 og kanten (v 1 , v 4 ).

Trinn 3. Siden toppunktet v 6 ikke er farget, utfører vi trinn 2, forutsatt at v = v 4.

a(v 2) = min (4, 3+¥) = 4,

a(v 3) = min (7, 3+¥) = 7,

a(v 5) = min (¥, 3+3) = 6,

a(v 6) = min (¥, 3+¥) = ¥.

Farg toppunktet v 2 og kanten (v 1 , v 2 ).

Trinn 3. Siden toppunktet v 6 ikke er farget, utfører vi trinn 2, forutsatt at v = v 2.

a(v 3) = min (7, 4+3) = 7,

a(v 5) = min (6, 4+2) = 6,

a(v 6) = min (¥, 4+¥) = ¥.

Farg toppunktet v 5 og kanten (v 4 , v 5 ).

Trinn 3. Siden toppunktet v 6 ikke er farget, utfører vi trinn 2, forutsatt at v = v 5.

a(v 3) = min (7, 6+¥) = 7,

a(v 6) = min (¥, 6+2) = 8.

Farg toppunktet v 3 og kanten (v 1 , v 3 ).

Trinn 3. Siden toppunktet v 6 ikke er farget, utfører vi trinn 2, forutsatt at v = v 3.

a(v 6) = min (8, 7+2) = 8.

Farg toppunktet v 6 og kanten (v 5 , v 6 ).

Siden toppunktet v 6 er farget, slutter vi å jobbe. Vi har fått en minimal rute v 1 v 4 v 5 v 6 , hvor lengden er 8 .

Merk at i dette tilfellet er dette ikke den eneste minimale ruten for hjørnene v 1 og v 6, siden i algoritmen var det mulig å farge i stedet for kanten (v 4, v 5) kanten (v 2, v 5), så ville vi få en annen rute av samme lengde.

4. Problemer på trær

En graf kalles asyklisk hvis den ikke har noen sykluser.

En graf uten sykluser kalles en skog.

Et tre er en sammenhengende asyklisk graf.

Å beregne avstander og bestemme ruter i en graf er et av de mest åpenbare og praktiske problemene som oppstår i grafteori. La oss introdusere noen nødvendige definisjoner.

Eksentrisitet grafisk toppunkt – avstanden til det maksimale toppunktet fra den. For en graf som den ikke er definert for vekt dens kanter, er avstanden definert som antall kanter.

Radius grafen er minimum eksentrisitet av toppunktene, og diameter graf – maksimal eksentrisitet av toppunkter.

Senter Grafen er dannet av toppunkter hvis eksentrisitet er lik radius. Sentrum av grafen kan bestå av ett, flere eller alle toppunktene i grafen.

Perifer toppunktene har en eksentrisitet lik diameteren.

En enkel kjede med lengde lik diameteren på grafen kalles diametral .

Teorem 12.1.I en tilkoblet graf er ikke diameteren større enn rangeringen av dens tilstøtende matrise.

Teorem 12.2.(Jordan) Hvert tre har et senter som består av ett eller to tilstøtende hjørner.

Teorem 12.3.Hvis diameteren på treet er jevn, har treet et enkelt senter, og alle diametralske kjeder passerer gjennom det hvis diameteren er oddetall, så er det to sentre og alle diametralske kjeder inneholder en kant som forbinder dem.

Den praktiske betydningen av grafsenteret er åpenbar. Hvis vi for eksempel snakker om en graf over veier med byknuder, så er det lurt å plassere et administrativt senter, varehus osv. i det matematiske senteret. Den samme tilnærmingen kan brukes på en vektet graf, der avstandene er vektene til kantene. Som vekt kan du ta den euklidiske avstanden, tiden eller kostnadene ved bevegelse mellom punktene.

Eksempel 12.5. Finn radius, diameter og sentrum av grafen vist i fig. 12.1.

Løsning. I denne oppgaven er det praktisk å bruke avstandsmatrise S. Et element i denne kvadratsymmetriske matrisen er lik avstanden mellom toppunktene jeg og toppen j. For grafen vist i fig. 12.1, har avstandsmatrisen følgende form:

. (12.2)

La oss beregne eksentrisiteten til hvert toppunkt. Denne verdien kan defineres som det maksimale elementet i den tilsvarende kolonnen i avstandsmatrisen (eller raden - siden matrisen S symmetrisk). Vi får

№

Grafradius r– minimum eksentrisitet av toppunktene. I dette tilfellet r= 2. Toppene nr. 2, nr. 4 og nr. 5 har en slik eksentrisitet. Tell diameter d– maksimal eksentrisitet av toppunktene. I dette tilfellet d= 3. Topper nr. 1 og nr. 3 har slik eksentrisitet dette er periferien av grafen. I den studerte grafen viste toppunktene seg å være enten sentrale eller perifere. I grafer av høyere orden er det andre toppunkter.

Eksentrisitetene til toppunktene til en liten graf kan enkelt beregnes ved direkte beregning fra tegningen. Imidlertid er grafen ikke alltid definert av utformingen. I tillegg kan grafen være stor. Derfor er det nødvendig med en annen måte å løse det forrige problemet på. Følgende teorem er kjent.

Teorem 12.4. La være tilstøtende matrisen til en graf G uten løkker og , Hvor . Da lik antall ruter med lengde k fra toppunkt til toppunkt.

Å løse grafteoretiske problemer ved å bruke ulike transformasjoner av tilstøtende matrisen kalles algebraisk metode .

Eksempel 12.6. Finn avstandsmatrisen til grafen vist i fig. 12.1, ved å bruke den algebraiske metoden.

Løsning. Nærhetsmatrisen til denne grafen er lik:

.

Vi vil fylle ut avstandsmatrisen ved å vurdere gradene til tilstøtningsmatrisen. Enhetene til tilstøtende matrisen viser par av hjørner som har en avstand på én mellom seg (det vil si at de er forbundet med en enkelt kant).

.

De diagonale elementene i avstandsmatrisen er null. Multipliser tilstøtende matrisen med seg selv:

.

I følge teoremet, mellom hjørnene 2 og 3, 1 og 4 osv. det er et visst antall ruter med lengde 2 (siden graden av matrisen er to). Antall ruter er ikke brukt her selve det faktum at en rute er tilstede og dens lengde er viktig, som indikert av ikke-null-elementet i matrisegraden, som ikke sammenfaller med elementet som er notert ved beregning av en rute av; kortere lengde. Vi legger 2 i de tomme elementene i avstandsmatrisen og får følgende tilnærming:

.

Avstanden mellom hjørnene 1 og 3 forblir ukjent. Vi vil multiplisere tilstøtende matrisen på seg selv til i matrisen ikke-null element vil ikke vises . Da er det tilsvarende elementet i avstandsmatrisen lik graden av tilstøtende matrisen: . På neste trinn får vi