Phenquestions
Een knoop in een graaf wordt een hoekpunt genoemd (meervoud - hoekpunten). Het wordt soms nog steeds een knooppunt genoemd; het kan ook een punt worden genoemd. Een link in een grafiek wordt een edge genoemd. Het wordt soms nog een link genoemd; het kan ook een lijn worden genoemd.
Grafiek met veel functies
Deze afbeelding toont een grafiek met veel functies:
De cirkels (schijven) zijn hoekpunten. Elke rechte lijn of gebogen lijn of lus is een rand.
Kenmerken van de grafiek
hoekpunt
Een hoekpunt is een object. Het kan een huis zijn; het kan een persoon zijn; het kan een abstract zelfstandig naamwoord zijn; het kan elk object zijn dat je maar kunt bedenken.
Rand
Een rand is een verbinding (relatie) tussen twee hoekpunten; de verbinding kan abstract zijn.
Lus
Een lus is een rand die een hoekpunt met zichzelf verbindt.
Pijlrand
Overweeg twee mensen: John en Peter. Als John Peter $ 100 leent, en als John en Peter hoekpunten zijn, dan wijst de uitleenkant naar Peter. Als beide partners vergeten dat Peter John iets schuldig is, en Peter leent John $ 100, dan wijst aan de andere kant van dezelfde rand een pijlpunt naar John. Als Peter maar $ 75 aan John leende en niet $ 100, dan zou een ander voordeel Peter met John verbinden. De pijlpunt van deze tweede rand wijst naar John. In het tweede geval zijn er twee randen, met elk één pijlpunt, die in tegengestelde richtingen wijzen.
Het hoekpunt waarnaar een rand wijst, is een hoofdpunt voor die rand. Het hoekpunt van waaruit een rand vertrekt, is een staartpunt.
Incident
Een rand verbindt twee hoekpunten. Er wordt gezegd dat de rand op beide hoekpunten invalt. De rand hoeft geen pijlpunt te hebben. De twee hoekpunten staan bekend als de eindpunten van de rand. Het is mogelijk om een grafiek te hebben waarbij een hoekpunt niet bij een rand hoort, maar daar wordt in deze tutorial geen rekening mee gehouden.
Ongerichte grafiek
Een rand kan een pijl zijn, of niet. Een grafiek waarbij geen rand een pijl is, is een ongerichte grafiek. Een rand kan worden weergegeven door een rechte lijn of een curve of een lus.
Gerichte grafiek
Een grafiek waarbij elke rand een pijl (richting) is, is een gerichte grafiek. Een pijlrand kan worden weergegeven door een rechte lijn met een pijlpunt of een curve met een pijlpunt of een lus met een pijlpunt.
De afwezigheid van een richting aan de rand van een ongerichte graaf, betekent dat elke rand van de ongerichte graaf bidirectioneel is.
Graad van een hoekpunt
Het aantal randen dat op een hoekpunt valt, is de graad van het hoekpunt. Een lus heeft twee incidenten op een hoekpunt, dus een lus wordt twee keer geteld.
Volgorde van een grafiek
De volgorde van een grafiek is het aantal hoekpunten in de grafiek.
Multigrafiek
Een multigraaf is een grafiek, waarbij voor sommige paren hoekpunten meer dan één rand is. Een ongerichte multigraaf is zo'n grafiek waarvan de randen geen richtingen hebben (geen pijlen). Een gerichte multigraaf is er een waarbij elke rand een pijl is, en voor paren hoekpunten die meer dan één pijl hebben, is één hoekpunt de staart van die pijlen en het andere hoekpunt is de kop van dezelfde pijlen. Het volgende diagram toont een ongerichte multigraaf:
Meer dan één randen (i.e. meerdere randen) voor een paar hoekpunten worden ook wel evenwijdige randen genoemd.
Pijlkoker
Een quiver is een multigraaf die lussen toestaat (een of meer lussen). Sommige multigrafieken staan geen lussen toe.
Eenvoudige grafiek
Een eenvoudige graaf is een graaf waarbij geen twee paar hoekpunten meerdere randen hebben. Lussen zijn niet toegestaan in een eenvoudige grafiek.
Lege grafiek
Een lege graaf is een graaf zonder hoekpunten en dus ook zonder randen.
Gemengde grafiek
Een gemengde grafiek is een grafiek waarbij sommige randen pijlen zijn en andere niet; met andere woorden: sommige randen hebben richtingen en andere zijn niet gericht.
Gewogen grafiek
Het is mogelijk om een grafiek te hebben waarin een getal, ook wel gewicht genoemd, aan elke rand wordt toegewezen. Sommige randen hebben hetzelfde nummer, maar de nummers zijn over het algemeen verschillend. Zo'n grafiek heet een gewogen grafiek. De getallen voor een bepaalde grafiek kunnen lengtes of kosten (prijzen) of een of andere grootte vertegenwoordigen, afhankelijk van het probleem.
Ingraad en buitengraad
De woordenschat, ingraad en uitgraad zijn alleen van toepassing op een gerichte graaf. De grafiek kan al dan niet een multigrafiek zijn. De grafiek kan al dan niet lussen hebben.
Het aantal pijlpunten verbonden met een hoekpunt is de ingraad van dat hoekpunt that. Een pijl met een enkele pijlpunt heeft een kop en een staart. Het aantal staarten verbonden met een hoekpunt is de buitengraad van dat hoekpunt ver.
Opmerking: een grafiek met meerdere randen voor het paar hoekpunten, waarbij de meerdere randen in tegengestelde richtingen zijn, wordt in deze zelfstudie niet behandeld.
Softwareweergave van een grafiek
Een grafiek kan in software worden weergegeven zoals deze in het diagram is getekend. Een grafiek kan in software ook worden weergegeven door een wiskundige matrix (tweedimensionale array). Een van dergelijke matrices wordt de aangrenzende matrix genoemd.
Aangrenzendheidsmatrix
Een aangrenzende matrix is een vierkante matrix. De koppen voor de rijen zijn alle hoekpunten, in oplopende volgorde geschreven. De koppen voor de kolommen zijn nog steeds dezelfde hoekpunten, in oplopende volgorde geschreven. Het tellen van de rijen of kolommen van een matrix begint bij 1 en niet bij nul zoals bij arrays. Bij het identificeren van een element in een matrix, wordt het rijnummer eerst vóór het kolomnummer geschreven.
Voor een ongerichte graaf is elk item (element) in de aangrenzende matrix het aantal randen dat de twee corresponderende hoekpunten verbindt. Een lus moet twee keer worden geteld. Voor een gerichte graaf is elke invoer in de aangrenzende matrix ofwel het aantal randen dat een rijpunt verlaat en het corresponderende kolompunt binnengaat, ofwel het aantal randen dat een kolompunt verlaat en het corresponderende rijpunt binnengaat. De keuze is aan de programmeur. In deze situatie (in beide gevallen) moet een lus nog steeds eenmaal worden geteld.
Opmerking: een grafiek is een diagram is een gegevensstructuur op zich. Een aangrenzende matrix is ook een datastructuur op zich.
Ongerichte grafiek en aangrenzende matrix
De volgende diagrammen tonen een ongerichte graaf en de bijbehorende aangrenzende matrix:
De leidende diagonaal van een matrix is de diagonaal van linksboven naar rechtsonder. Een ongerichte matrix is symmetrisch om de leidende diagonaal. De matrixinvoer voor rij A en kolom C is 1, wat betekent dat er één rand is die hoekpunt A en hoekpunt C . verbindt. De matrixinvoer voor rij C en kolom B is 3, wat betekent dat er 3 randen zijn die hoekpunt C en hoekpunt B verbinden. De andere vermeldingen worden op dezelfde manier uitgelegd.
De som van de invoeren voor een rij geeft het aantal randen (graden) voor het corresponderende hoekpunt. De som van de invoeren voor rij A is 2, wat betekent dat 2 randen verbonden zijn met hoekpunt A. De som van de invoeren voor rij B is 6, wat betekent dat 6 randen verbonden zijn met hoekpunt B. De rest van de inzendingen worden op dezelfde manier uitgelegd.
Gerichte grafiek en aangrenzende matrix
De volgende diagrammen tonen een gerichte grafiek en de bijbehorende aangrenzende matrix:
De aangrenzende matrix voor een gerichte graaf is niet noodzakelijk symmetrisch ten opzichte van de leidende diagonaal. De matrixinvoer voor rij A en kolom C is 1, wat betekent dat één rand vertrekt van hoekpunt A naar hoekpunt C. De matrixinvoer voor rij C en kolom B is 3, wat betekent dat er 3 randen vertrekken van hoekpunt C naar hoekpunt B. De andere vermeldingen worden op dezelfde manier uitgelegd.
De som van de items voor een kolom geeft de ingraad voor het (kolom) hoekpunt. De som van de invoeren voor een rij geeft de outdegree voor het (rij) hoekpunt. De som van de items voor kolom A is 1, wat betekent dat één rand naar hoekpunt A . is gericht. De som van de invoeren voor rij B is 2, wat betekent dat 2 randen vertrekken vanaf hoekpunt B. De rest van de inzendingen worden op dezelfde manier uitgelegd.
Grafiekbewerkingen
Een gegevensstructuur, zoals een grafiek, bestaat uit een reeks gegevenswaarden of een reeks objecten, plus de relatie tussen de objecten, plus de bewerkingen (functies) tussen de objecten. De relaties in een grafiek worden aangegeven door de randen. Verder moet een grafiek in ieder geval de volgende bewerkingen hebben:
aangrenzend (G, x, y)
G betekent grafiek. Deze bewerking verifieert of een rand hoekpunt x en hoekpunt y verbindt. De waarde en positie van een item in een matrix geven de verbinding van een rand (en het type) aan.
buren(G, x)
Deze bewerking retourneert een lijst van alle hoekpunten die direct zijn verbonden met het hoekpunt x. De waarde en positie van een invoer in een matrix geven de verbinding van een rand aan.
remove_vertex(G, x)
Deze bewerking verwijdert een hoekpunt, x uit een grafiek. Als het hoekpunt geen rand had, is er geen probleem. Als het hoekpunt echter links had, moeten de links (randen) ook worden verwijderd. De waarde en positie van een item in een matrix geven de aanwezigheid van een bepaald hoekpunt aan. Als een hoekpunt wordt verwijderd, moet de matrix opnieuw worden aangepast.
add_vertex(G, x)
Dit voegt een hoekpunt toe, x zonder randen toe te voegen, of vervangt een hoekpunt dat randen had maar was verwijderd. De waarde en positie van een item in een matrix geven de aanwezigheid van een bepaald hoekpunt aan. Als een hoekpunt wordt toegevoegd, moet de matrix opnieuw worden aangepast.
add_edge(G, x, y)
Deze bewerking voegt een nieuwe rand toe tussen het hoekpunt x en het hoekpunt y als de rand er niet was. De waarde en positie van een item in een matrix geven de aanwezigheid van een bepaalde rand aan. Als een rand wordt toegevoegd, moet de matrix opnieuw worden aangepast.
remove_edge(G, x, y)
Deze bewerking zou de rand tussen het hoekpunt x en het hoekpunt y verwijderen als de rand er was. De waarde en positie van een item in een matrix geven de aanwezigheid van een bepaalde rand aan. Als een rand wordt verwijderd, moet de matrix opnieuw worden afgesteld.
get_vertex_value(G, x)
Deze bewerking retourneert de waarde, v geassocieerd met het hoekpunt, x. Om dit te bereiken, hebt u een vermogensset van subsets nodig voor hoekpuntlabels en hun waarden.
set_vertex_value(G, x, v)
Deze bewerking geeft een nieuwe waarde, v voor de waarde die bij het hoekpunt hoort, x. Om dit te bereiken, hebt u een vermogensset van subsets nodig voor hoekpuntlabels en hun waarden.
Sommige grafieken koppelen waarden ook aan hun randen. Dergelijke grafieken hebben de volgende aanvullende bewerkingen nodig:
get_edge_value(G, x, y)
Deze bewerking retourneert de waarde, v geassocieerd met de rand, (x, y). Om dit te bereiken, heb je een machtsset van subsets voor randen en hun waarden nodig.
set_edge_value(G, x, y, v)
Deze bewerking geeft een nieuwe waarde, v voor de waarde die bij de rand hoort, (x, y). Om dit te bereiken, heb je een machtsset van subsets voor randen en hun waarden nodig.
Conclusie
Een grafiek is een verzameling hoekpunten verbonden met randen. Een grafiek kan ongericht of gericht zijn. De randen kunnen niet-directioneel of directioneel zijn;. Lussen kunnen aanwezig of afwezig zijn in een grafiek. Wat u vervolgens moet leren, is set, power set en multiset met betrekking tot grafieken. Daarna moet je de verschillende soorten grafieken leren, zoals een georiënteerde grafiek, gewone grafiek, volledige grafiek, tweedelige grafiek, toernooigrafiek, stroomnetwerkgrafiek, enz.
Chrys
Over de auteur
Chrysanthus Forcha
Ontdekker van wiskunde Integratie van First Principles en aanverwante series. Master's degree in technisch onderwijs, gespecialiseerd in elektronica en computersoftware. BSc Elektronica. Ik heb ook kennis en ervaring op masterniveau in Informatica en Telecommunicatie. Van de 20.000 schrijvers was ik de 37e beste schrijver bij devarticles.com. Ik werk al meer dan 10 jaar op deze gebieden.
Bekijk alle berichten
