Wat is grafentheorie en hoe wordt een grafiek als zodanig gedefinieerd?

In 1736 werd op basis van het werk van de Zwitserse natuurkundige-wiskundige Leonhard Euler (1707-1783) waargenomen dat een opeenvolging van hoekpunten definieert een pad, maar als dat pad uit verschillende hoekpunten bestaat zonder herhalende randen, wordt het een pad of pad genoemd euleriaans; als we bovendien bij het startpunt aankomen, waarbij we elke rand slechts één keer doorlopen, dan hebben we een Euleriaanse cyclus (circuit).

Citaat (APA)

alexander barraza | juli. 2022
Graad in natuurkunde

Van zijn kant definiëren we een grafiek als een geordend paar (GOES) waar v geeft de (niet-lege) verzameling van alle hoekpunten of knopen van een graaf aan, terwijl EEN geeft de verzameling aan (deze kan leeg zijn) van alle randen of lijnen die de hoekpunten van een grafiek verbinden. De elementen van de set EEN kan worden aangeduid als een ongeordend paar {v, w} waarbij v en w elementen (knopen of hoekpunten) zijn van v, op deze manier wordt dan gezegd dat v en w aangrenzende hoekpunten zijn (ze zijn verbonden door een rand).

Grafentheorie komt voort uit het antwoord dat Euler gaf op een probleem van populaire vindingrijkheid dat zich afvroeg hoe de zeven bruggen over te steken die toegetreden tot twee eilanden van de gemeenschap van Königsberg (destijds deel van Duitsland, en momenteel Kaliningrad, in Rusland), tussen hen en met het vasteland zonder twee te gebruiken keer dezelfde brug en aankomen op het startpunt (gelegen op het vasteland), wat het ook mag zijn, bepalen dat in dit geval uiteindelijk geen kon.

Het probleem van de zeven bruggen van Königsberg

Euler modelleerde Königsberg als een grafiek waarbij elk punt (vertex of knoop) een brug vertegenwoordigt en elke lijn (rand) een pad op het land:

Wat is de oplossing voor dit probleem?

er is er geen oplossing die aan de opgelegde voorwaarden voldoet, aangezien, zoals Euler aantoonde, de hoekpunten niet even graad zijn, dat wil zeggen, een even aantal lijnen heeft geen invloed op elk punt _[3]. Het lijkt erop dat we echter niet veel kunnen doen met een structuur die zo eenvoudig is gedefinieerd, zoals vaak het geval is in wiskunde, Soms zijn dingen niet wat ze lijken. Dus een van de meest productieve, transversale en interdisciplinaire gebieden _[4] van menselijke kennis, grafentheorie.

Euleriaanse grafieken of met Euleriaanse baan?

De volgende grafieken hebben allemaal Euleriaanse paden _[5]. Hebben ze allemaal Euleriaanse cycli?

Laten we de derde grafiek nemen:

Laten we de hoekpunten nummeren:

We zien dan dat het pad gedefinieerd door de rij {3,4,6,2,1,3,7,6,5,4,2} een Euleriaans pad is, aangezien het gaat door de hele grafiek zonder herhalende randen, maar het is geen Euleriaanse cyclus, omdat het het startpunt niet bereikt. Wat zou er gebeurd zijn als we de hoekpunten anders hadden genummerd? Niet veel, behalve dat het pad nu bepaald zou worden door een andere opeenvolging. Wat zou er zijn gebeurd als we andere paden hadden gevolgd dan die in onze oorspronkelijke oplossing waren voorgesteld? Deze vraag is een beetje ingewikkelder om te beantwoorden, en het gaat om algoritmen waar software-ingenieurs meestal blij mee zijn. programmeren.

Voor een meer rigoureus bewijs van wat hier wordt blootgelegd, moeten we verwijzen naar het volgende resultaat:

"Zijn G een verbonden grafiek _[6]. Dan ja G heb een circuit Euler, de graad van elk hoekpunt is even, terwijl als G heeft een Euler-pad, G heeft precies twee hoekpunten van oneven graad _[7] (precies de hoekpunten waar het pad begint en eindigt)".

We kunnen dan verifiëren dat in de grafiek die we nemen in feite alleen de hoekpunten 3 en 6 een oneven graad hebben (dit zou voorkomen, zelfs als de nummering van de hoekpunten anders was geweest), daarom heeft de graaf een pad euleriaans _[8]. Voor de overige grafieken kunnen we op analoge manier te werk gaan en verifiëren of ze inderdaad paden hebben en Euleriaanse cycli, of anders gezegd, kunnen we zulke grafieken tekenen zonder het potlood op te pakken en te herhalen? lijnen? Het antwoord op deze vraag kan worden afgeleid uit wat tot nu toe al is uitgelegd, maar het is een oefening interessant in termen van fijne motoriek, vindingrijkheid en geduld, ik nodig de lezer uit om grafieken van 6 of meer te zoeken en te tekenen hoekpunten met traject Eulerian.

Zijn er andere soorten grafieken? Heeft grafentheorie toepassingen in de 'echte' wereld?

Deze grafieken die we heel kort hebben besproken, zijn slechts een van de vele soorten grafieken die we in de grafentheorie aantreffen. We kunnen ook grafieken vinden zoals bomen, zeer representatief in sets waar hun elementen kunnen worden geclassificeerd in hiërarchieën en in telberekeningen en waarschijnlijkheid_[9], digraphs, Hamiltoniaanse grafieken _[10], enz.

Afbeelding van grafische modellen en netwerken in Psycho., door Ruiz, Ana María.

Deze raadsels, als we ze zo willen noemen, hebben een enorme toepasbaarheid in de wereld van vandaag, in situaties die zo divers zijn als: biologie moleculair _[11], computergebruik_[12], telecommunicatie _[13] en netwerkanalyse _[14]. Het is dan de moeite waard om te vragen: Is het niet op zijn minst merkwaardig dat een probleem van een bijna... banaal uiteindelijk een van de meest interessante en opvallende resultaten van de wiskunde zal zijn? Misschien was hiervoor de bijdrage van een van de meest illustere geesten van de mensheid nodig.