Konstruer en så komplet graf som muligt. Konstruktion af grafer baseret på deres egenskaber

Teoretisk information

Bemærk, at i konstruktionsproblemer skal løsningen søges blandt simple urettede grafer (dvs. grafer uden flere kanter og uden sløjfer). Desværre er der ingen universel teknik, der giver dig mulighed for præcist at bestemme, om en graf med givne karakteristika kan konstrueres.

Det er vigtigt at huske, at i enhver graf er summen af graderne af alle dens hjørner et lige tal, lig med to gange antallet af kanter på grafen, da hver kant deltager i denne sum nøjagtigt to gange. Dette resultat, kendt af Euler for 200 år siden, kaldes ofte håndtrykslemmaet. Det følger heraf, at hvis flere personer giver hånd, så er det samlede antal håndtryk nødvendigvis lige, fordi der er to hænder involveret i hvert håndtryk (hver hånd tælles lige så mange gange, som den deltog i håndtryk). Den følger det:

antallet af hjørner med ulige grader i enhver graf er lige;
i enhver graf med P tinder hvor P> 2, er der altid mindst to hjørner med samme grader;
hvis i en graf med hjørner p> 2 nøjagtigt to toppunkter har samme grad, så er der i denne graf altid enten nøjagtigt et toppunkt af grad 0 eller nøjagtigt et toppunkt af grad (S - 1).

Når du løser problemer, skal du læse betingelserne meget omhyggeligt, da mange adjektiver, der beskriver egenskaberne for en graf, har numeriske ækvivalenter. Vi præsenterer en tabel over sådanne overensstemmelser, der oftest findes i problemformuleringen (tabel 2.9).

Når du har fået alle de nødvendige tal, skal du prøve at beregne de manglende karakteristika for grafen. Nogle gange giver tilstanden graderne af alle eller flere hjørner. I dette tilfælde, baseret på det faktum, at hver kant af grafen tilføjer nøjagtigt to hjørner til sin samlede grad, kan vi bruge formlen

X 5 (y/) =2t'

Hvor T - antal toppunkter, og summeringen udføres over alle toppunkter fra 1 til P.

Opgaver

Opgave 2.42. Konstruer en graf på otte toppunkter, der har følgende fordeling af toppunktsgrader: to toppunkter af grad 4; tre hjørner af grad 3; to spidser af grad 2; et toppunkt af grad 1.

Løsning.

Den samlede grad af alle hjørner er 2-4 + 3- 3 + 2- 2+1 1=22, hvilket betyder, at der er 11 kanter i alt. Det er lettere at bygge grafer baseret på en vektor af grader, startende fra hjørner med store grader. Ver-

Tabel 2.9

Overensstemmelse mellem beskrivelsen af en graf og dens egenskaber

Adjektiv	Tal	Hvad betyder det
		Grafen har præcis én tilsluttet komponent
Usammenhængende		Grafen har mere end én komponent, dens diameter er nøjagtigt lig med uendelig
Fast	5(U;) = SOSHI	Graderne af alle toppunkter er lige store
Almindelig grad	з(Уі)=У	Graderne af alle toppunkter er lige store u. Hvis kendt P(antal toppunkter), så kan du med det samme beregne T(antal ribben): y-p? y/2 (P eller på skal være et lige tal)
Acyklisk	y= t-p + k = 0	Det cyklomatiske tal er nul, grafen har ingen cyklusser, det er et træ eller en skov (afhængigt af tilslutningsmuligheder), sådanne grafer kan altid farves i to farver. Hvis to ud af tre variable er kendt ( P, t, k), så ved hjælp af formlen kan du finde det resterende
Træ (eller acyklisk forbundet graf)	y=t-n+ 1 = 0, hvorfra T- n - 1	Det cyklomatiske tal er nul, grafen har ingen cyklusser, det er et træ, sådanne grafer kan altid farves i to farver. Hvis en af to variable er kendt ( P eller T), så ved hjælp af formlen kan du finde den anden
Bikromatisk		Det kromatiske tal for en graf er to, sådanne grafer kan altid farves i to farver, disse er todelte grafer, grafisk er de enten acykliske grafer eller grafer, hvor alle cyklusser har en lige længde

Det er bedre at arrangere busserne i den grafiske repræsentation af grafen, så så få kanter og buer skærer hinanden som muligt, og selve hjørnerne er grupperet efter et eller andet lighedskriterium. En af mulighederne er vist i fig. 2.8.

Opgave 2.43. Konstruer en graf på seks toppunkter, der har følgende fordeling af toppunktsgrader: to toppunkter af grad 3;

Ris. 2.8.

to spidser af grad 2; et toppunkt af grad 1; et toppunkt har en vilkårlig grad.

Løsning.

Den samlede grad af toppunkterne er 11, derfor skal det resterende toppunkt have en ulige grad, dvs. 1,3 eller 5. Det er således muligt at konstruere tre forskellige grafer (fig. 2.9).

Ris. 2.9.

Opgave 2.44. Konstruer en graf med følgende vektor af toppunktsgrader: 5 = (1, 2, 2, 3, 4, 4, 5).

Løsning.

Den samlede grad er 5 + 8 + 3 + 4+1=21. Da dette er et ulige tal, hvilket er i modstrid med sætningen (antallet af kanter er halvdelen af dette tal, men 21 er ikke ligeligt deleligt med 2).

Svar. Der findes ikke en sådan graf.

Opgave 2.45. Konstruer en graf med følgende vektor af toppunktsgrader: 5 = (1, 1,2, 2, 2, 4, 4, 4, 4).

Opgave 2.46. Konstruer en graf med følgende vektor af toppunktsgrader: 5 = (5, 5, 6, 6, 6, 6, 6).

Opgave 2.47. Konstruer en graf med følgende vektor af toppunktsgrader: 5 = (1, 1, 1,2, 3, 3, 3, 3, 5, 5, 5).

Opgave 2.48. Konstruer en graf med følgende vektor af toppunktsgrader: 5 = (3, 3, 3, 3, 3, 3, 3, 7).

Opgave 2.49. Konstruer en graf på seks toppunkter, der har følgende fordeling af toppunkter: tre toppunkter er af grad 5, og de andre tre toppunkter er af ukendt grad.

Opgave 2.50. Konstruer en graf på ti toppunkter med dobbelt så mange kanter som toppunkter og følgende fordeling af toppunkter: to toppunkter med grad 6; fire hjørner af grad 5; to spidser af grad 4; to hjørner af vilkårlig grad - eller retfærdiggøre umuligheden af at konstruere en sådan graf.

Opgave 2.51. Konstruer en graf på ti toppunkter, der har følgende fordeling af toppunktsgrader: et toppunkt på grad 7; to spidser af grad 6; to spidser af grad 5; to spidser af grad 4; to spidser af grad 3; et toppunkt af grad 2 - eller retfærdiggøre umuligheden af at konstruere en sådan graf.

Opgave 2.52. Konstruer en graf på 11 toppunkter, der har følgende fordeling af toppunktsgrader: et toppunkt på grad 7; to spidser af grad 6; to spidser af grad 5; to spidser af grad 4; to spidser af grad 3; et toppunkt af grad 2 - eller retfærdiggøre umuligheden af at konstruere en sådan graf.

Grafteori er en gren af diskret matematik, der studerer objekter repræsenteret som individuelle elementer (hjørnepunkter) og forbindelser mellem dem (buer, kanter).

Grafteori stammer fra løsningen af problemet med Königsberg-broerne i 1736 af den berømte matematiker Leonard Euler(1707-1783: født i Schweiz, boede og arbejdede i Rusland).

Problem om Königsberg-broerne.

Der er syv broer i den preussiske by Königsberg ved Pregal-floden. Er det muligt at finde en vandrerute, der krydser hver bro præcis én gang og starter og slutter samme sted?

En graf, hvor der er en rute, der starter og slutter ved samme toppunkt og passerer langs alle grafens kanter nøjagtigt én gang, kaldesEuler graf.

Rækkefølgen af hjørner (måske gentages), som den ønskede rute passerer igennem, såvel som selve ruten, kaldesEuler cyklus .

Problemet med tre huse og tre brønde.

Der er tre huse og tre brønde, på en eller anden måde placeret på et fly. Tegn en sti fra hvert hus til hver brønd, så stierne ikke krydser hinanden. Dette problem blev løst (det blev vist, at der ikke er nogen løsning) af Kuratovsky (1896 - 1979) i 1930.

De fire farver problem. Opdeling af et fly i ikke-skærende områder kaldes med kort. Kortområder kaldes tilstødende, hvis de har en fælles grænse. Opgaven er at farvelægge kortet på en sådan måde, at ikke to tilstødende områder er malet med samme farve. Siden slutningen af det 19. århundrede har man kendt en hypotese om, at fire farver er nok til dette. Hypotesen er endnu ikke bevist.

Essensen af den offentliggjorte løsning er at prøve et stort, men begrænset antal (ca. 2000) typer potentielle modeksempler til firefarvesætningen og vise, at ikke et enkelt tilfælde er et modeksempel. Denne søgning blev afsluttet af programmet på omkring tusind timers supercomputerdrift.

Det er umuligt at kontrollere den resulterende løsning "manuelt" - omfanget af opregning er uden for rammerne af menneskelige evner. Mange matematikere rejser spørgsmålet: kan et sådant "programbevis" betragtes som et gyldigt bevis? Der kan jo være fejl i programmet...

Vi kan således kun stole på forfatternes programmeringsevner og tro, at de gjorde alt rigtigt.

Definition 7.1. Tælle G= G(V, E) er en samling af to endelige mængder: V – kaldet mange hjørner og sættet E af par af elementer fra V, dvs. EÍV´V, kaldet mange kanter, hvis parrene er uordnede, eller mange buer, hvis parrene er bestilt.

I det første tilfælde grafen G(V, E) hedder uorienteret, i den anden – orienteret.

EKSEMPEL. En graf med et sæt toppunkter V = (a,b,c) og et sæt kanter E =((a, b), (b, c))

EKSEMPEL. En graf med V = (a,b,c,d,e) og E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (c, d)),

Hvis e=(v 1 ,v 2), еОЕ, så siger de, at kanten er e forbinder hjørner v 1 og v 2.

To hjørner v 1,v 2 kaldes tilstødende, hvis der er en kant, der forbinder dem. I denne situation kaldes hvert af hjørnerne utilsigtet hændelse tilsvarende kant .

To forskellige ribben tilstødende, hvis de har et fælles toppunkt. I denne situation kaldes hver af kanterne tilfældigt tilsvarende toppunkt .

Antal grafens toppunkter G lad os betegne v, og antallet af kanter er e:

Den geometriske repræsentation af graferne er som følger:

1) toppunktet på grafen er et punkt i rummet (på planet);

2) en kant af en urettet graf – et segment;

3) en bue af en rettet graf – et rettet segment.

Definition 7.2. Hvis der i kanten e=(v 1 ,v 2) forekommer v 1 =v 2, så kaldes kanten e sløjfe. Hvis en graf tillader sløjfer, kaldes den graf med løkker eller pseudograf .

Hvis en graf tillader mere end én kant mellem to hjørner, kaldes den multigraf .

Hvis hvert hjørne af en graf og/eller kant er mærket, kaldes en sådan graf markeret (eller indlæst ). Bogstaver eller heltal bruges normalt som mærker.

Definition 7.3. Kurve G (V , E ) hedder underafsnit (eller en del ) kurve G(V,E), hvis V V, E E. Hvis V = V, At G hedder spændende undergraf G.

Eksempel 7 . 1 . Givet en urettet graf.

Definition 7.4. Grafen kaldes komplet , hvis nogen dens to hjørner er forbundet med en kant. Komplet graf med n hjørner er betegnet med K n .

tæller K 2 , TIL 3, TIL 4 og K 5 .

Definition 7.5. Kurve G=G(V, E) Hedder tokimbladede , hvis V kan repræsenteres som en forening af usammenhængende sæt, f.eks V=ENB, så hver kant har formen ( v jeg , v j), Hvor v jeg EN Og v j B.

Hver kant forbinder et toppunkt fra A til et toppunkt fra B, men ingen to toppunkter fra A eller to toppunkter fra B er forbundet.

En todelt graf kaldes komplet tokimblad tælle K m , n, hvis EN indeholder m toppe, B indeholder n hjørner og for hver v jeg EN, v j B vi har ( v jeg , v j)E.

Altså for alle v jeg EN, Og v j B der er en kant, der forbinder dem.

K 12 K 23 K 22 K 33

Eksempel 7 . 2 . Konstruer en komplet todelt graf K 2.4 og hele grafen K 4 .

Enhedsgrafn-dimensionel terningI n .

Hjørnerne på grafen er n-dimensionelle binære mængder. Kanter forbinder hjørner, der adskiller sig i én koordinat.

Eksempel:

Et grafikfilformat er en måde at repræsentere grafiske data på eksterne medier. Der er raster- og vektorformater af grafiske filer, blandt hvilke der igen er universelle grafiske formater og proprietære (originale) formater af grafiske applikationer.

Universelle grafikformater "forstås" af alle applikationer, der arbejder med raster (vektor) grafik.

Det universelle rastergrafikformat er BMR-formatet. Grafiske filer i dette format har en stor informationsvolumen, da de tildeler 24 bits til at gemme information om farven på hver pixel.

Tegninger gemt i det universelle bitmapformat GIF kan kun bruge 256 forskellige farver. Denne palet er velegnet til simple illustrationer og piktogrammer. Grafikfiler i dette format har en lille informationsvolumen. Dette er især vigtigt for grafik, der bruges på World Wide Web,

brugere gerne vil have de oplysninger, de har bedt om, skal vises på skærmen så hurtigt som muligt.

Det universelle rasterformat JPEG er designet specielt til effektiv lagring af billeder i fotografisk kvalitet. Moderne computere kan gengive mere end 16 millioner farver, hvoraf de fleste simpelthen ikke kan skelnes for det menneskelige øje. JPEG-formatet giver dig mulighed for at kassere de forskellige farver på nabopixels, der er "overdrevne" for menneskelig opfattelse. Nogle af de originale oplysninger går tabt, men dette sikrer en reduktion i informationsvolumen (komprimering) af den grafiske fil. Brugeren får mulighed for at bestemme graden af filkomprimering. Hvis billedet, der gemmes, er et fotografi, der skal udskrives på et ark i stort format, er tab af information uønsket. Hvis dette fotografi placeres på en XL-side, kan det sikkert komprimeres ti gange: den resterende information vil være nok til at gengive billedet på monitorskærmen.

Universal vektorgrafikformater inkluderer WMF-formatet, der bruges til at gemme en samling af Microsoft-billeder (http://office.microsoft.com/ru-ru/clipart).

Det universelle EPS-format giver dig mulighed for at gemme information om både raster- og vektorgrafik. Det bruges ofte til import! filer ind i programmer til klargøring af trykte produkter.

Du vil blive fortrolig med dine egne formater direkte i processen med at arbejde med grafiske applikationer. De giver det bedste forhold mellem billedkvalitet og filinformationsvolumen, men understøttes (dvs. genkendes og afspilles) kun af programmet selv, der opretter filen.

Opgave 1. 3 bytes bruges til at kode en pixel. Billedet, der måler 2048 x 1536 pixels, blev gemt som en ukomprimeret fil. Bestem størrelsen på den resulterende fil. Løsning.

I-k.i i-I/k

i-2. 1024 8/(128. 128) =

2 2 10 2 3 /(2 7 2 7) = 2 1 + 10 + 3 /2 7 + 7 2 14 /2 14 = 1 (bit). LG-21-2.

Svar: 2 farver - sort og hvid.

DEN VIGTIGSTE

Computergrafik er et bredt begreb, der refererer til: 1) forskellige typer grafiske objekter, der er skabt eller behandlet ved hjælp af computere; 2) et aktivitetsområde, hvor computere bruges som værktøjer til at skabe og behandle grafiske objekter.

Afhængigt af metoden til at skabe et grafisk billede, skelnes raster- og vektorgrafik.

I rastergrafik dannes et billede som et raster af en samling af prikker (pixels), der danner rækker og kolonner. Når et rasterbillede gemmes i computerens hukommelse, gemmes oplysninger om farven på hver pixel, der er inkluderet i det.

I vektorgrafik dannes billeder på basis af datasæt (vektorer), der beskriver et bestemt grafisk objekt og formler for deres konstruktion. Når du gemmer et vektorbillede, indtastes information om de enkleste geometriske objekter, der udgør det, i computerens hukommelse.

a Spørgsmål og opgaver

1. Hvad er computergrafik?

2. Angiv de vigtigste anvendelsesområder for computergrafik.

H. Hvordan kan digital grafik fremstilles?

4. Et farvebillede, der måler 10 x 15 cm, scannes Scanneropløsningen er 600 x 600 dpi, farvedybde - 3 bytes. Hvilken informationsmængde vil den resulterende grafikfil have?

5. Hvad er forskellen mellem raster- og vektormetoder til at repræsentere et billede?

b. Hvorfor menes det, at rasterbilleder formidler farver meget præcist?

7. Hvilken operation med at konvertere et rasterbillede fører til det største tab af dets kvalitet - reduktion eller forstørrelse? Hvordan kan du forklare dette?

8. Hvorfor påvirker skalering ikke kvaliteten af vektorbilleder?

9. Hvordan kan du forklare de mange forskellige grafiske filformater?

Computer grafik

10. Hvad er hovedforskellen mellem universelle grafikformater og proprietære grafikapplikationsformater?

11. Konstruer en så fuldstændig graf som muligt for begreberne i afsnit 3.2.4.

12. Giv en detaljeret beskrivelse af raster- og vektorbilleder, med angivelse af følgende:

a) af hvilke elementer billedet er bygget;

b) hvilke oplysninger om billedet er lagret i ekstern hukommelse;

c) hvordan størrelsen af en fil, der indeholder et grafisk billede, bestemmes;

d) hvordan billedkvaliteten ændres ved skalering;

e) hvad er de vigtigste fordele og ulemper ved raster (vektor) billeder.

13. En tegning på 1024 x 512 pixels blev gemt som en ukomprimeret fil på 1,5 MB. Hvor meget information blev brugt til at kode pixlens farve? Hvad er det maksimalt mulige antal farver i en palet svarende til denne farvedybde?

14. Et ukomprimeret rasterbillede på 256 x 128 pixels optager 16 KB hukommelse. Hvad er det maksimalt mulige antal farver i billedpaletten?

Grafteori- en af de mest omfattende grene af diskret matematik, meget udbredt til løsning af økonomiske og ledelsesmæssige problemer, i programmering, kemi, design og undersøgelse af elektriske kredsløb, kommunikation, psykologi, psykologi, sociologi, lingvistik og andre vidensområder. Grafteori studerer systematisk og konsekvent egenskaberne ved grafer, som kan siges at bestå af sæt af punkter og sæt af linjer, der repræsenterer sammenhængene mellem disse punkter. Grundlæggeren af grafteorien anses for at være Leonhard Euler (1707-1882), som løste det dengang velkendte problem med Königsberg-broerne i 1736.

Der bygges grafer for at vise relationer på sæt. Lad for eksempel være et sæt EN = {-en1 , -en 2 , ... -en n)- mange mennesker, og hvert element vil blive vist som en prik. En masse B = {b1 , b 2 , ... b m)- mange forbindelser (lige linjer, buer, segmenter - det betyder ikke noget endnu). På sæt EN bekendtskabsforholdet mellem personer fra dette sæt er givet. Opbygning af en graf fra punkter og forbindelser. Links vil forbinde par af mennesker, der kender hinanden. Naturligvis kan antallet af bekendtskaber for nogle mennesker afvige fra antallet af bekendte med andre mennesker, og nogle kender måske ikke nogen (sådanne elementer vil være punkter, der ikke er forbundet med andre). Så vi har en graf!

Det, vi først kaldte "punkter", skulle kaldes grafens hjørner, og det, vi kaldte "forbindelser", skulle kaldes grafens kanter.

Grafteori tager ikke højde for den specifikke karakter af mængder EN Og B. Der er en lang række meget forskellige specifikke problemer, når man løser, som man midlertidigt kan glemme alt om det specifikke indhold af sæt og deres elementer. Denne specificitet påvirker ikke på nogen måde fremskridtet med at løse problemet, uanset dets vanskelighed! For eksempel når man skal afgøre, om det er muligt fra et punkt -en kom til sagen e, der kun bevæger sig langs linjerne, der forbinder punkterne, er det ligegyldigt, om vi har at gøre med mennesker, byer, tal osv. Men når problemet er løst, får vi en løsning, der er sand for ethvert indhold, der er modelleret som en graf. Det er derfor ikke overraskende, at grafteori er et af de mest populære værktøjer til at skabe kunstig intelligens: når alt kommer til alt, kan kunstig intelligens diskutere spørgsmål om kærlighed, spørgsmål om musik eller sport og spørgsmål om løsning af forskellige problemer med en samtalepartner. , og gør dette uden nogen overgang (switching) , uden hvilken en person ikke kan undvære i sådanne tilfælde.

Og nu de strenge matematiske definitioner af en graf.

Definition 1.Det kaldes en graf et system af objekter af vilkårlig karakter (hjørnepunkter) og links (kanter), der forbinder nogle par af disse objekter.

Definition 2. Lade V– (ikke-tom) sæt af hjørner, elementer v∈V- toppe. Kurve G = G(V) med mange hjørner V der er en bestemt familie af par af formen: e = (-en, b) , Hvor -en,b∈V , der angiver, hvilke hjørner der forbliver forbundet. Hvert par e = (-en, b) - kanten af grafen. En masse U- mange kanter e kurve. Toppe -en Og b– kantens endepunkter e .

Grafer som datastruktur. Den udbredte brug af grafteori i datalogi og informationsteknologi skyldes tilføjelsen af begrebet graf som datastruktur til ovenstående definitioner. I datalogi og informationsteknologi er en graf defineret som en ikke-lineær datastruktur. Hvad er så en lineær datastruktur, og hvordan adskiller grafer sig fra dem? Lineære datastrukturer er kendetegnet ved, at de forbinder elementer gennem relationer af typen "simple naboskab". Lineære datastrukturer er for eksempel arrays, tabeller, lister, køer, stakke, strenge. I modsætning hertil er ikke-lineære datastrukturer dem, hvor elementer er placeret på forskellige niveauer i hierarkiet og er opdelt i tre typer: original, genereret og lignende. Så en graf er en ikke-lineær datastruktur.

Ordet graf er af græsk oprindelse, fra ordene "jeg skriver", "jeg beskriver". Fra begyndelsen af denne artikel ved vi, hvad grafen præcis beskriver: den beskriver sammenhænge. Det vil sige, at enhver graf beskriver sammenhænge. Og omvendt: enhver sammenhæng kan beskrives som en graf.

Grundlæggende begreber i grafteori

Begrebet forekomst er også nødvendigt, når man udvikler algoritmer til løsning af mange praktiske problemer med grafer. Du kan for eksempel sætte dig ind i softwareimplementeringen dybde-første gennemløb af grafen repræsenteret af incidensmatricen. Ideen er enkel: du kan kun bevæge dig gennem hjørner forbundet med kanter. Og hvis nogle værdier er tildelt til kanterne ("skalaer", oftest i form af tal, kaldes sådanne grafer vægtede eller mærkede), så kan komplekse anvendte problemer løses, hvoraf nogle er nævnt i sidste afsnit af denne lektion.

Klassiske problemer med grafteori og deres løsninger

Et af de første offentliggjorte eksempler på arbejde med grafteori og anvendelse af grafer er arbejdet med "Königsberg Bridges Problem" (1736), forfattet af den eminente matematiker fra det 18. århundrede Leonhard Euler. Problemet indeholder en flod, øer, der skylles af denne flod, og flere broer. Spørgsmål til problemet: er det muligt, efter at have forladt et bestemt punkt, kun at krydse hver bro én gang og vende tilbage til udgangspunktet? (billede nedenfor)

Problemet kan modelleres som følger: Et punkt er knyttet til hvert landområde, og to punkter er forbundet med en linje, hvis og kun hvis de tilsvarende landområder er forbundet med en bro (figur nedenfor, forbindelseslinjer er tegnet med stiplede linjer) . Dermed er grafen konstrueret.

Eulers svar på problemspørgsmålet er som følger. Hvis dette problem havde en positiv løsning, ville der i den resulterende graf være en lukket sti, der passerer langs kanterne og kun indeholder hver kant én gang. Hvis der findes en sådan sti, skal hvert toppunkt kun have et lige antal kanter. Men den resulterende graf har toppunkter, der har et ulige antal kanter. Derfor har problemet ikke en positiv løsning.

Ifølge etableret tradition er en Eulersk graf en graf, hvor det er muligt at krydse alle hjørnerne og samtidig kun krydse en kant én gang. I den skal hvert toppunkt kun have et lige antal kanter. Et problem med middel sværhedsgrad på Euler-grafer er i materialet "Grundlæggende grafer".

I 1847 udviklede Kirchhoff teorien om træer for at løse et simultant system af lineære algebraiske ligninger, så man kan finde værdien af strømmen i hver leder (bue) og i hvert kredsløb i et elektrisk kredsløb. Ud fra elektriske kredsløb og kredsløb, der indeholder modstande, kondensatorer, induktanser osv., betragtede han de tilsvarende kombinatoriske strukturer, der kun indeholder toppunkter og forbindelser (kanter eller buer), og for forbindelser er der ingen grund til at tage hensyn til, hvilke typer elektriske elementer de svarer til. Kirchhoff erstattede således hvert elektrisk kredsløb med en tilsvarende graf og viste, at for at løse et ligningssystem er det ikke nødvendigt at overveje hver cyklus af den elektriske kredsløbsgraf separat.

Cayley opdagede i 1858, mens han arbejdede med rent praktiske problemer i organisk kemi, en vigtig klasse af grafer kaldet træer. Han søgte at liste isomererne af mættede kulbrinter med et givet antal kulstofatomer. Cayley formulerede først problemet abstrakt: find antallet af alle træer med s knudepunkter, som hver har spidser med grader 1 og 4. Han var ikke i stand til umiddelbart at løse dette problem, og han begyndte at ændre dets formulering på en sådan måde, at et nyt opregningsproblem kunne løses:

rodfæstede træer (hvor et af hjørnerne er valgt);
alle træer;
træer, hvis topgrader ikke overstiger 4;
træer, hvis toppunktsgrader er 1 og 4 (udtalelse af et problem fra kemi).

Tegn problemer for at forstærke grundlæggende begreber

Eksempel 1. Lade EN- sæt af tal 1, 2, 3: EN= (1, 2, 3). Konstruer en graf for at vise sammenhængen "

Løsning. Det er klart, at tallene 1, 2, 3 skal repræsenteres som hjørnerne af en graf. Derefter skal hvert par hjørner forbindes med en kant. Ved at løse dette problem kom vi til sådanne grundlæggende begreber inden for grafteori som rettede og urettede grafer. Urettede grafer er dem, hvis kanter ikke har nogen retning. Eller, som de siger endnu oftere, rækkefølgen af de to ender af en kant er ikke signifikant. Faktisk behøver grafen, der er konstrueret i begyndelsen af denne lektion og afspejler bekendtskabsforholdet mellem mennesker, ikke kantretninger, da det kan argumenteres, at "person nummer 1" er bekendt med "person nummer 2" i samme grad som "person nummer 2" med "person nummer 1". I vores nuværende eksempel er et tal mindre end et andet, men ikke omvendt. Derfor skal den tilsvarende kant af grafen have en retning, der angiver, hvilket tal der er mindre end det andet. Det vil sige, at rækkefølgen af kantenderne er væsentlig. En sådan graf (med kanter med en retning) kaldes en rettet graf eller digraf.

Altså i vores mangfoldighed EN nummer 1 er mindre end nummer 2 og nummer 3, og nummer 2 er mindre end nummer 3. Vi viser dette faktum ved kanter, der har en retning, som er vist med pile. Vi får følgende graf:

Eksempel 2. Lade EN- sæt af numre 2, 4, 6, 14: EN= (2, 4, 6, 14). Opret en graf for at vise "delelig med"-relationen på dette sæt.

Løsning. I dette eksempel vil nogle af kanterne have en retning, og nogle vil ikke, det vil sige, vi bygger blandet graf. Lad os liste relationerne i mængden: 4 er deleligt med 2, 6 er deleligt med 2, 14 er deleligt med 2, og hvert tal fra dette sæt er deleligt med sig selv. Denne relation, det vil sige når et tal er deleligt med sig selv, vil blive vist i form af kanter, der forbinder toppunktet med sig selv. Sådanne kanter kaldes sløjfer. I dette tilfælde er det ikke nødvendigt at give retning til løkken. Så i vores eksempel er der tre regulære rettede kanter og fire løkker. Vi får følgende graf:

Eksempel 3. Lad givne sæt EN= (α, β, γ) og B= (a, b, c). Konstruer en graf for at vise forholdet "kartesisk produkt af mængder."

Løsning. Som det er kendt fra definitionen Kartesisk produkt af sæt, er der ingen ordnede sæt af elementer i det samme sæt. Det vil sige, at i vores eksempel kan du ikke kombinere græske bogstaver med græsk og latin med latin. Dette faktum vises som todelt graf, altså en, hvor spidserne er delt i to dele, således at spidserne, der hører til den samme del, ikke er forbundet med hinanden. Vi får følgende graf:

Eksempel 4. Ejendomsmægleren beskæftiger lederne Igor, Sergey og Peter. Objekter O1, O2, O3, O4, O5, O6, O7, O8 serviceres. Konstruer en graf for at vise relationerne "Igor arbejder med objekter O4, O7", "Sergey arbejder med objekter O1, O2, O3, O5, O6", "Peter arbejder med objekt O8".

Løsning. Grafen, der viser disse relationer, vil også være todelt, da lederen ikke arbejder med lederen og objektet ikke arbejder med objektet. Men i modsætning til det foregående eksempel vil grafen være rettet. Faktisk arbejder Igor for eksempel med objekt O4, men objekt O4 virker ikke med Igor. Ofte, når en sådan egenskab ved relationer er indlysende, kan behovet for at give retning til kanterne virke som "matematisk dumhed." Men stadig, og dette følger af matematikkens strenge natur, hvis forholdet er ensidigt, er det nødvendigt at give anvisninger til kanterne. I relationelle applikationer betaler denne stringens sig for eksempel i programmer designet til planlægning, hvor der også bruges grafer, og ruten langs spidser og kanter skal passere strengt i en given retning. Så vi får følgende rettede todelte graf:

Og igen til eksempler med tal.

Eksempel 5. Lad et sæt blive givet C = {2, 3, 5, 6, 15, 18} . Konstruer en graf, der implementerer en relation, der definerer alle par af tal -en Og b fra mange C, hvori, når vi dividerer det andet element med det første, får vi en kvotient, der er et heltal større end 1.

Løsning. Grafen, der viser disse relationer, vil være orienteret, da betingelsen indeholder en omtale af det andet og det første element, det vil sige, at kanten vil blive rettet fra det første element til det andet. Heraf er det klart, hvilket element der er det første og hvilket andet. Lad os også tilføje noget terminologi: orienterede kanter kaldes normalt buer. Der vil være 7 buer i vores graf: e1 = (3, 15) , e2 = (3, 18) , e3 = (5, 15) , e4 = (3, 6) , e5 = (2, 18) , e6 = (6, 18) , e7 = (2, 6) . I dette eksempel er grafens kanter (buer) simpelthen nummereret, men serienumre er ikke det eneste, der kan tildeles en bue. Buen kan også tildeles skalaer, der for eksempel betyder omkostningerne ved at sende last fra et punkt til et andet. Men vi vil stifte bekendtskab med buevægte senere og mere detaljeret. Så vi får følgende rettede graf:

Som vi allerede ved fra den teoretiske indledende del, tager grafteori ikke højde for mængders specifikke karakter og ved hjælp af samme graf er det muligt at definere relationer på mængder med meget forskelligt indhold. Det vil sige, at netop dette indhold kan abstraheres fra, når man modellerer en opgave. Lad os gå videre til eksempler, der illustrerer denne bemærkelsesværdige egenskab ved grafteori.

Eksempel 6. På et stykke af et skakbræt, der måler 3 X 3, placeres to hvide riddere og to sorte riddere som vist på nedenstående figur.

Er det muligt at flytte ridderne til tilstanden vist i følgende figur uden at glemme, at to brikker ikke kan være på samme felt?

Løsning. I den konstruerede graf vil par af knudepunkter være forbundet med "riddertræk"-relationen. Det vil sige, at det ene toppunkt er det, hvorfra ridderen forlod, og det andet er det, det ankom til, og den mellemliggende celle af bogstavet "r" vil være uden for dette forhold. Vi får følgende graf:

Og alligevel viste designet sig at være besværligt. Cellerne på et skakbræt er synlige i det, og mange af grafens kanter skærer hinanden. Er det muligt at abstrahere fra skakbrættets fysiske udseende og forestille sig forholdet mere enkelt? Det viser sig, at det er muligt. I den nye graf vil de tilstødende hjørner være dem, der er forbundet med "riddertræk"-forholdet, og ikke dem, der er nabostillede på skakbrættet (figur nedenfor).

Nu er det let at se, at svaret på spørgsmålet om dette problem er negativt. I den oprindelige tilstand er der ingen sort ridder mellem to hvide riddere, men i den endelige tilstand skal der være denne sorte ridder. Kanterne på grafen er placeret, så to tilstødende riddere ikke kan hoppe over hinanden.

Eksempel 7. Problemet med ulven, geden og kålen. På den ene bred af floden er der en mand (H), en båd, en ulv (V), en ged (Kz) og en kål (Kp). En person og ikke mere end en af de transporterede genstande må være i båden på samme tid. En person skal transportere alle genstande til den anden side og observere tilstanden: en ulv må ikke efterlades uden opsyn med en ged og en ged med kål.

Løsning. I den konstruerede graf er hjørnerne konfigurationer, og kanterne er "forbindelsen med en bådtur"-forholdet mellem konfigurationerne. Konfiguration refererer til arrangementet af objekter på den oprindelige bank og på den modsatte bank. Hver konfiguration vises som ( EN|B) , Hvor EN- genstande placeret på den oprindelige kyst, og B- genstande placeret på den modsatte bred. Den indledende konfiguration er derfor - (PMCpKz| ) . For eksempel, efter at have transporteret en ged til den anden side, vil konfigurationen være (VKp|ChKz) . Den endelige konfiguration er altid ( |PMCpKz) . Nu kan vi bygge en graf, idet vi allerede ved, hvad hjørnerne og kanterne betyder:

Lad os placere toppunkterne på grafen, så kanterne ikke skærer hinanden, og de tilstødende toppunkter er dem, der er forbundet med et forhold på grafen. Så vil det være meget nemmere at se relationerne (for at forstørre billedet, venstreklik på det):

Som vi kan se, er der to forskellige kontinuerlige ruter fra den indledende konfiguration til den endelige. Derfor har problemet to forskellige løsninger (og begge er korrekte).

Grafteori og de vigtigste moderne anvendte problemer

Med udgangspunkt i grafteori er der udviklet metoder til løsning af anvendte problemstillinger, hvor meget komplekse systemer modelleres i form af grafer. I disse modeller indeholder noder individuelle komponenter, og kanter repræsenterer forbindelser mellem komponenter. Typisk bruges vægtede grafer til at modellere transportnetværk, køsystemer og netværksplanlægning. Vi har allerede talt om dem, det er grafer, hvor der er tildelt vægte til buerne.

Trægrafer bruges for eksempel til at konstruere beslutningstræer(tjener til risikoanalyse, analyse af mulige gevinster og tab under usikkerhedsforhold). Ved hjælp af grafteori udviklede og andre talrige matematiske modeller at løse problemer inden for specifikke fagområder.

Grafer og flowproblemet

Formulering af problemet. Der er et system af vandrør, repræsenteret ved grafen i figuren nedenfor.

Hver bue af grafen repræsenterer et rør. Tallene over buerne (skalaerne) er rørkapaciteten. Noder er steder, hvor rør er forbundet. Vand strømmer gennem rør i kun én retning. Knude S- vandkilde, knudepunkt T- lager. Det er nødvendigt for at maksimere mængden af vand, der strømmer fra kilde til afløb.

For at løse flowproblemet kan du bruge Ford-Fulkerson-metoden. Ideen med metoden: søgningen efter det maksimale flow udføres i trin. I begyndelsen af algoritmen er flowet sat til nul. Ved hvert efterfølgende trin stiger værdien af flowet, hvortil der søges en komplementær vej, gennem hvilken det yderligere flow kommer. Disse trin gentages, så længe der findes yderligere stier. Problemet er med succes blevet anvendt i forskellige distribuerede systemer: strømforsyningssystem, kommunikationsnetværk, jernbanesystem og andre.

Grafer og netværksplanlægning

Ved planlægning af problemer med komplekse processer, der består af mange job, hvoraf nogle udføres parallelt og nogle sekventielt, er vægtede grafer, kendt som PERT-netværk, blevet meget brugt.

PERT - Program (Project) Evaluation and Review Technique - en teknik til at evaluere og analysere programmer (projekter), som bruges i projektledelse.

PERT-netværket er en vægtet acyklisk rettet graf, hvor hver bue repræsenterer et job (handling, operation), og vægten af buen er den tid, det tager at fuldføre det.

Hvis der er buer i netværket ( -en, b) Og ( b, c), derefter værket repræsenteret af buen ( -en, b) skal være afsluttet før arbejdet repræsenteret af buen ( b, c). Hvert toppunkt ( vjeg) repræsenterer det tidspunkt, hvor alt arbejde, defineret af buer, der slutter ved et toppunkt ( vjeg).

I en kolonne som denne:

et toppunkt, der ikke har nogen forgængere, bestemmer starttidspunktet for arbejdet;
et toppunkt, som ikke har nogen tilhængere, svarer til det tidspunkt, hvor sættet af værker er afsluttet.

Stien med maksimal længde mellem disse hjørner af grafen (fra begyndelsen til slutningen af arbejdsprocessen) kaldes den kritiske vej. For at reducere den tid, der kræves for at fuldføre hele komplekset af arbejdet, er det nødvendigt at finde arbejde, der ligger på den kritiske vej, og reducere dets varighed ved for eksempel at tiltrække yderligere kunstnere, mekanismer og nye teknologier.

Hele blokken "Graph Theory"

Det er tilrådeligt at introducere begrebet graf, efter at flere problemer svarende til opgave 1 er blevet analyseret, hvor den afgørende betragtning er grafisk repræsentation. Det er vigtigt, at eleverne straks indser, at den samme graf kan tegnes på forskellige måder. Efter min mening er der ingen grund til at give en streng definition af en graf, fordi det er for besværligt og vil kun komplicere diskussionen. I første omgang vil et intuitivt koncept være tilstrækkeligt. Når man diskuterer begrebet isomorfi, kan man løse flere øvelser for at identificere isomorfe og ikke-isomorfe grafer. Et af de centrale punkter i emnet er sætningen om pariteten af antallet af ulige toppunkter. Det er vigtigt, at eleverne fuldt ud forstår dets bevis og lærer at anvende det til problemløsning. Når man analyserer flere problemer, anbefaler jeg, at man ikke refererer til sætningen, men faktisk gentager dets bevis. Konceptet med grafforbindelse er også ekstremt vigtigt. En meningsfuld overvejelse her er hensynet til forbindelseskomponenten, der skal lægges særlig vægt på dette. Euler-grafer er nærmest et spilemne.

Det første og vigtigste mål, der skal forfølges, når man studerer grafer, er at lære skolebørn at se grafen i problemformuleringen og korrekt oversætte betingelsen til grafteoriens sprog. Du bør ikke fortælle dem begge til alle i flere klasser i træk. Det er bedre at sprede klasserne over 2-3 akademiske år. (Vedhæftet er udviklingen af lektionen "Begrebet graf. Anvendelse af grafer til opgaveløsning" i 6. klasse).

2. Teoretisk materiale til emnet "Graffer".

Introduktion

Grafer er vidunderlige matematiske objekter med deres hjælp kan du løse en masse forskellige, udadtil forskellige problemer. Der er et helt afsnit i matematik - grafteori, som studerer grafer, deres egenskaber og anvendelser. Vi vil kun diskutere de mest grundlæggende begreber, egenskaber ved grafer og nogle måder at løse problemer på.

Koncept af en graf

Lad os overveje to problemer.

Opgave 1. Rumkommunikation er blevet etableret mellem de ni planeter i solsystemet. Regelmæssige raketter flyver på følgende ruter: Jorden - Merkur; Pluto - Venus; Jorden - Pluto; Pluto - Kviksølv; Merkur - Wien; Uranus - Neptun; Neptun - Saturn; Saturn – Jupiter; Jupiter - Mars og Mars - Uranus. Er det muligt at flyve på almindelige raketter fra Jorden til Mars?

Løsning: Lad os tegne et diagram over tilstanden: vi vil afbilde planeterne som punkter og raketruterne som linjer.

Nu står det straks klart, at det er umuligt at flyve fra Jorden til Mars.

Opgave 2. Tavlen har form som et dobbelt kors, som fås ved at fjerne hjørnefirkanterne fra en 4x4 firkant.

Er det muligt at omgå det ved at flytte en skak-ridder og vende tilbage til det oprindelige felt og besøge alle felterne nøjagtigt én gang?

Løsning: Lad os nummerere kvadraterne på tavlen sekventielt:

Og nu, ved hjælp af figuren, vil vi vise, at en sådan gennemgang af tabellen, som angivet i betingelsen, er mulig:

Vi overvejede to forskellige problemer. Løsningerne på disse to problemer er dog forenet af en fælles idé – en grafisk repræsentation af løsningen. Samtidig viste de tegnede billeder til hver opgave sig at ligne hinanden: Hvert billede består af flere prikker, hvoraf nogle er forbundet med linjer.

Sådanne billeder kaldes grafer. Punkterne kaldes toppe, og linjerne – ribben kurve. Bemærk, at ikke alle billeder af denne type vil blive kaldt en graf. For eksempel. hvis du bliver bedt om at tegne en femkant i din notesbog, så vil en sådan tegning ikke være en graf. Vi vil kalde en tegning af denne type, som i de foregående opgaver, en graf, hvis der er en specifik opgave, som en sådan tegning er konstrueret til.

En anden note vedrører grafens udseende. Prøv at kontrollere, at grafen for den samme opgave kan tegnes på forskellige måder; og omvendt, til forskellige opgaver kan du tegne grafer af samme udseende. Det eneste, der betyder noget her, er, hvilke hjørner der er forbundet med hinanden, og hvilke der ikke er. For eksempel kan grafen for opgave 1 tegnes anderledes:

Sådanne identiske, men forskelligt tegnede grafer kaldes isomorf.

Grader af hjørner og optælling af antallet af kanter på en graf

Lad os nedskrive en definition mere: Graden af et toppunkt i en graf er antallet af kanter, der kommer ud fra det. I denne henseende kaldes et toppunkt med en lige grad et lige toppunkt, henholdsvis et toppunkt med en ulige grad kaldes et ulige toppunkt.

En af grafteoriens hovedsætninger er relateret til begrebet toppunktsgrad - teoremet om retfærdigheden af antallet af ulige toppunkter. Vi vil bevise det lidt senere, men først, til illustration, vil vi overveje problemet.

Opgave 3. Der er 15 telefoner i byen Malenky. Er det muligt at forbinde dem med ledninger, så hver telefon er forbundet med præcis fem andre?

Løsning: Lad os antage, at en sådan forbindelse mellem telefoner er mulig. Forestil dig så en graf, hvor hjørnerne repræsenterer telefoner, og kanterne repræsenterer ledningerne, der forbinder dem. Lad os tælle, hvor mange ledninger der er i alt. Hver telefon har præcis 5 ledninger tilsluttet, dvs. graden af hvert hjørne af vores graf er 5. For at finde antallet af ledninger skal du opsummere graderne af alle hjørnerne på grafen og dividere det resulterende resultat med 2 (da hver ledning har to ender, så når du summerer graderne, tages hver ledning 2 gange) . Men så vil antallet af ledninger være anderledes. Men dette tal er ikke et heltal. Det betyder, at vores antagelse om, at hver telefon kan tilsluttes præcis fem andre, viste sig at være forkert.

Svar. Det er umuligt at forbinde telefoner på denne måde.

Sætning: Enhver graf indeholder et lige antal ulige hjørner.

Bevis: Antallet af kanter på en graf er lig med halvdelen af summen af graderne af dens hjørner. Da antallet af kanter skal være et heltal, skal summen af graderne af hjørnerne være lige. Og dette er kun muligt, hvis grafen indeholder et lige antal ulige hjørner.

Grafforbindelse

Der er et andet vigtigt koncept relateret til grafer - begrebet tilslutning.

Grafen kaldes sammenhængende, hvis to af dens hjørner kan forbindes ved, de der. kontinuerlig række af kanter. Der er en række problemer, hvis løsning er baseret på konceptet grafforbindelse.

Opgave 4. Der er 15 byer i landet Seven, hver by er forbundet med veje til mindst syv andre. Bevis, at det er moderigtigt at komme fra hver by til enhver anden.

Bevis: Overvej to vilkårlige byer A og B og antag, at der ikke er nogen vej mellem dem. Hver af dem er forbundet med veje til mindst syv andre, og der er ingen by, der er forbundet med begge de pågældende byer (ellers ville der være en sti fra A til B). Lad os tegne en del af grafen, der svarer til disse byer:

Nu er det tydeligt synligt, at vi har modtaget mindst 16 forskellige byer, hvilket modsiger problemets forhold. Det betyder, at udsagnet er blevet bevist ved selvmodsigelse.

Hvis vi tager den tidligere definition i betragtning, kan udsagnet af problemet omformuleres på en anden måde: "Bevis, at vejgrafen for landet Syv er forbundet."

Nu ved du, hvordan en forbundet graf ser ud. En afbrudt graf har form af flere "stykker", som hver er enten et separat vertex uden kanter eller en forbundet graf. Du kan se et eksempel på en afbrudt graf i figuren:

Hver sådan individuel brik kaldes forbundet komponent af grafen. Hver tilsluttet komponent repræsenterer en forbundet graf, og alle de udsagn, som vi har bevist for forbundne grafer, holder for den. Lad os se på et eksempel på et problem, der bruger en tilsluttet komponent:

Opgave 5. I Far Far Away Kingdom er der kun én type transport - et flyvende tæppe. Der er 21 tæppelinjer, der forlader hovedstaden, en fra byen Dalniy og 20 fra alle andre byer. Bevis, at du kan flyve fra hovedstaden til byen Dalniy.

Bevis: Det er klart, at hvis du tegner en graf over kongerigets tæppe, kan den være usammenhængende. Lad os se på forbindelseskomponenten, der inkluderer Kongerigets hovedstad. Der kommer 21 tæpper ud af hovedstaden, og 20 fra enhver anden by undtagen byen Dalniy, derfor er det nødvendigt, for at loven om et lige antal ulige hjørner skal være opfyldt, at byen Dalniy medtages i den samme forbindelseskomponent. Og da den tilsluttede komponent er en forbundet graf, så er der fra hovedstaden en sti langs tæpperne til byen Dalniy, hvilket var det, der skulle bevises.

Euler grafer

Du har sikkert stødt på opgaver, hvor du skal tegne en form uden at løfte blyanten fra papiret og kun tegne hver streg én gang. Det viser sig, at et sådant problem ikke altid er løst, dvs. Der er figurer, der ikke kan tegnes ved hjælp af denne metode. Spørgsmålet om løseligheden af sådanne problemer indgår også i grafteorien. Det blev først udforsket i 1736 af den store tyske matematiker Leonhard Euler, der løste problemet med Königsberg-broerne. Derfor kaldes grafer, der kan tegnes på denne måde, Euler-grafer.

Opgave 6. Er det muligt at tegne grafen vist på figuren uden at løfte blyanten fra papiret og tegne hver kant nøjagtigt én gang?

Løsning. Hvis vi tegner grafen som angivet i betingelsen, så vil vi indtaste hvert hjørne, undtagen de indledende og sidste, det samme antal gange, som vi forlader det. Det vil sige, at alle hjørner af grafen, undtagen to, skal være lige. Vores graf har tre ulige hjørner, så den kan ikke tegnes på den måde, der er angivet i betingelsen.

Nu har vi bevist teoremet om Euler-grafer:

Sætning: En Euler-graf må højst have to ulige hjørner.

Og afslutningsvis - problemet med Königsberg-broerne.

Opgave 7. Figuren viser et diagram over broer i byen Königsberg.

Er det muligt at gå en tur, så man krydser hver bro præcis én gang?

3. Problemer for emnet "Graffer"

Konceptet med en graf.

1. På et 3x3 firkantet bræt placeres 4 riddere som vist i Fig. 1. Er det muligt, efter at have foretaget flere træk med ridderne, at omarrangere dem til positionen vist i fig. 2?

Ris. 1

Ris. 2

Løsning. Lad os nummerere kvadraterne på brættet som vist på figuren:

Lad os tildele et punkt på flyet til hver celle, og hvis en celle kan nås ved at flytte en skakridder fra en celle, så forbinder vi de tilsvarende punkter med en linje. Den indledende og påkrævede placering af ridderne er vist i figurerne:

For enhver sekvens af riddertræk kan deres rækkefølge naturligvis ikke ændres. Derfor er det umuligt at omarrangere hestene på den nødvendige måde.

2. I landet Digit er der 9 byer med navnene 1, 2, 3, 4, 5, 6, 7, 8, 9. En rejsende opdagede, at to byer er forbundet af et flyselskab, hvis og kun hvis det tocifrede tal dannet af navnene byer, divideret med 3. Er det muligt at flyve fra by 1 til by 9?

Løsning. Ved at tildele en prik til hver by og forbinde prikkerne med en linje, hvis summen af tallene er delelig med 3, får vi en graf, hvor tallene 3, 5, 9 er forbundet med hinanden, men ikke forbundet med hvile. Det betyder, at du ikke kan flyve fra by 1 til by 9.

Grader af hjørner og optælling af antallet af kanter.

3. Der er 100 byer i en stat, og hver by har 4 veje. Hvor mange veje er der i staten?

Løsning. Lad os tælle det samlede antal veje, der forlader byen - 100 . 4 = 400. Men med denne beregning tælles hver vej 2 gange - den forlader en by og kommer ind i en anden. Det betyder, at der i alt er to gange færre veje, dvs. 200.

4. Der er 30 personer i klassen. Kan det være, at 9 personer har 3 venner, 11 har 4 venner, og 10 har 5 venner?

Svar. Nej (sætningen om pariteten af antallet af ulige hjørner).

5. Kongen har 19 vasaller. Kan det være, at hver vasal har 1, 5 eller 9 naboer?

Svar. Nej han kan ikke.

6. Kan en stat, hvor præcis 3 veje udgår fra hver by have præcis 100 veje?

Løsning. Lad os tælle antallet af byer. Antallet af veje er lig med antallet af byer x ganget med 3 (antallet af veje, der forlader hver by) og divideret med 2 (se opgave 3). Så er 100 = 3x/2 => 3x = 200, hvilket ikke kan ske med naturligt x. Det betyder, at der ikke kan være 100 veje i sådan en tilstand.

7. Bevis, at antallet af mennesker, der nogensinde har levet på Jorden og lavet et ulige antal håndtryk, er lige.

Beviset følger direkte af sætningen om pariteten af antallet af ulige toppunkter i en graf.

Forbindelse.

8. I landet forlader 100 veje hver by, og fra hver by kan du komme til enhver anden. Den ene vej var spærret for reparation. Bevis, at du nu kan komme fra enhver by til enhver anden.

Bevis. Lad os overveje forbindelseskomponenten, som omfatter en af byerne, hvor vejen mellem var lukket. Ved sætningen om pariteten af antallet af ulige hjørner inkluderer den også den anden by. Det betyder, at du stadig kan finde en rute og komme fra en af disse byer til en anden.

Euler grafer.

9. Der er en gruppe øer forbundet med broer, så man fra hver ø kan komme til en hvilken som helst anden. Turisten gik rundt på alle øerne og krydsede hver bro én gang. Han besøgte Threefold Island tre gange. Hvor mange broer fører fra Troyekratnoye hvis en turist

a) startede ikke med det og sluttede ikke med det?
b) startede med det, men blev ikke færdigt med det?
c) startede med det og sluttede med det?

10. Billedet viser en park opdelt i flere dele af hegn. Er det muligt at gå gennem parken og dens omgivelser, så man kan klatre over hvert hegn én gang?