Phenquestions
En nod i en graf kallas en toppunkt (plural - vertices). Ibland kallas det fortfarande en nod; det kan också kallas en punkt. En länk i en graf kallas en kant. Ibland kallas det fortfarande en länk; det kan också kallas en linje.
Diagram med många funktioner
Denna figur visar en graf med många funktioner:
Cirklarna (skivorna) är hörn. Varje rak linje eller böjd linje eller slinga är en kant.
Funktioner i diagrammet
Vertex
Ett toppunkt är ett objekt. Det kan vara ett hus; det kan vara en person; det kan vara ett abstrakt substantiv; det kan vara vilket objekt du än kan tänka dig.
Kant
En kant är en förbindelse (relation) mellan två hörn; anslutningen kan vara abstrakt.
Slinga
En slinga är en kant som ansluter ett toppunkt till sig själv.
Pilkanten
Tänk på två personer: John och Peter. Om John lånar Peter $ 100, och om John och Peter är hörn, kommer utlåningskanten att peka mot Peter. Om båda parter glömmer att Peter är skyldig John och Peter lånar John 100 dollar, kommer en pilspets i andra änden av samma kant att peka mot John. Om Peter bara lånade 75 dollar till John och inte 100 dollar, skulle en annan kant ansluta Peter till John. Denna andra kant kommer att ha sin pilspets mot John. I det andra fallet finns det två kanter med en pilspets vardera som pekar i motsatta riktningar.
Det toppunkt som en kant pekar mot är ett huvudpunkt för den kanten. Spetsen från vilken en kant lämnar är en svansspets.
Incident
En kant förbinder två hörn. Kanten sägs inträffa på vardera vertex. Kanten behöver inte ha en pilspets. De två hörnpunkterna är kända som ändpunkterna för kanten. Det är möjligt att ha ett diagram där ett toppunkt inte tillhör någon kant, men det kommer inte att beaktas i denna handledning.
Oriktad graf
En kant kan vara en pil eller inte. Ett diagram där ingen kant är en pil är ett oriktat diagram. En kant kan representeras av en rak linje eller en kurva eller en slinga.
Regisserad graf
Ett diagram där varje kant är en pil (riktning) är en riktad graf. En pilkant kan representeras av en rak linje med en pilspets eller en kurva med en pilspets eller en slinga med en pilspets.
Frånvaron av en riktning på kanten av en icke-riktad graf, betyder att varje kant av den icke-riktade grafen är dubbelriktad.
Vertexgrad
Antalet kanter som inträffar på en topp är graden av toppunkten. En slinga har två förekomster på en topp, så en slinga räknas två gånger.
Ordning på en graf
Ordningen på ett diagram är antalet hörn i diagrammet.
Multigraph
Ett multigraph är ett diagram, där det för flera par av hörn finns mer än en kant. En oriktad multigraf är en sådan graf där kanterna inte har några riktningar (är inte pilar). En riktad multigraph är en där varje kant är en pil, och för par av hörn som har mer än en pil, är en topp ett svans på dessa pilar, och det andra toppet är huvudet på samma pilar. Följande diagram visar en oriktad multigraf:
Mer än ena kanterna (i.e. flera kanter) för ett par hörn kallas också parallella kanter.
Koger
En quiver är ett multigraph som tillåter loopar (en eller flera loopar). Vissa multigrafier tillåter inte öglor.
Enkel graf
En enkel graf är en graf där inga två par av hörn har flera kanter. Slingor är inte tillåtna i ett enkelt diagram.
Tom graf
Ett tomt diagram är ett diagram utan hörn och så inga kanter.
Blandad graf
Ett blandat diagram är ett diagram där vissa kanter är pilar och andra inte; med andra ord: vissa kanter har riktningar och andra är inte riktade.
Vägt diagram
Det är möjligt att ha ett diagram där ett tal, så kallat vikt, tilldelas varje kant. Vissa kanter har samma antal, men siffrorna är i allmänhet olika. En sådan graf kallas ett viktat diagram. Siffrorna för ett visst diagram kan representera längder eller kostnader (priser) eller storlek av något slag, beroende på problemet.
Indegree och Outdegree
Ordförrådet, indegree och outgrad är endast tillämpligt på en riktad graf. Grafen kan vara multigraf eller inte. Grafen kan ha loopar eller inte.
Antalet pilspetsar som är kopplade till ett toppunkt är indegraden för det toppunktet. En pil med en enda pilspets har en huvudände och en svansände. Antalet svansar som är anslutna till ett toppunkt är utegraden för det toppunktet.
Obs! Ett diagram med flera kanter för paret av hörn, där flera kanter är i motsatta riktningar, behandlas inte i denna handledning.
Programvarurepresentation av en graf
En graf kan visas i programvaran så som den ritas i diagrammet. En graf kan också representeras i programvaran av en matematisk matris (tvådimensionell matris). En av sådana matriser kallas angränsningsmatris.
Adjacency matris
En angränsande matris är en kvadratisk matris. Rubrikerna för raderna är alla hörn, skrivna i stigande ordning. Rubrikerna för kolumnerna är fortfarande samma hörn, skrivna i stigande ordning. Räkning av rader eller kolumner i en matris börjar från 1 och inte noll som med matriser. När du identifierar ett element i en matris skrivs radnumret först före kolumnnumret.
För en oriktad graf är varje post (element) i angränsningsmatrisen antalet kanter som förbinder de två motsvarande hörnpunkterna. En slinga bör räknas två gånger. För en riktad graf är varje post i angränsningsmatrisen antingen antalet kanter som lämnar en radhörn och går in i motsvarande kolumnhörn eller är antalet kanter som lämnar en kolumnhörn och går in i motsvarande radhörn. Valet är valet för programmeraren. I denna situation (i båda fallen) bör en slinga fortfarande räknas en gång.
Obs: En graf är ett diagram är en datastruktur i sig. En angränsande matris är också en datastruktur i sig.
Oriktad matris för diagram och adjacency
Följande diagram visar en oriktad graf och motsvarande angränsningsmatris:
Den ledande diagonalen för en matris är diagonalen från övre vänster till nedre höger. En oriktad matris är symmetrisk om den ledande diagonalen. Matrisposten för rad A och kolumn C är 1, vilket innebär att det finns en kant som förbinder toppunkt A och toppunkt C. Matrisposten för rad C och kolumn B är 3, vilket innebär att det finns 3 kanter som förbinder toppunkt C och topp B. De andra posterna förklaras på samma sätt.
Summan av posterna för en rad ger antalet kanter (grad) för motsvarande toppunkt. Summan av posterna för rad A är 2, vilket betyder att två kanter är kopplade till toppunkt A. Summan av posterna för rad B är 6, vilket betyder att 6 kanter är kopplade till toppunkt B. Resten av posterna förklaras på samma sätt.
Regisserad matris för graf och adjacency
Följande diagram visar en riktad graf och motsvarande angränsningsmatris:
Angränsningsmatrisen för en riktad graf är inte nödvändigtvis symmetrisk om den ledande diagonalen. Matrisposten för rad A och kolumn C är 1, vilket innebär att en kant lämnar från topp A till topp C. Matrisposten för rad C och kolumn B är 3, vilket betyder att 3 kanter går från topp C till topp B. De andra posterna förklaras på samma sätt.
Summan av posterna för en kolumn ger indegrammet för (kolumn) toppunkten. Summan av posterna för en rad ger utgraderingen för (rad) toppunkten. Summan av posterna för kolumn A är 1, vilket innebär att en kant riktas mot toppunkt A. Summan av posterna för rad B är 2, vilket betyder att två kanter lämnar från topp B. Resten av posterna förklaras på samma sätt.
Grafoperationer
En datastruktur, såsom en graf, består av en uppsättning datavärden eller en uppsättning objekt, plus förhållandet mellan objekten, plus operationerna (funktionerna) mellan objekten. Förhållandena i ett diagram indikeras av kanterna. På det borde en graf ha åtminstone följande operationer:
intill (G, x, y)
G betyder diagram. Denna åtgärd verifierar om en kant ansluter toppunkt x och toppunkt y. Värdet och positionen för en post i en matris anger anslutningen av en kant (och dess typ).
grannar (G, x)
Den här åtgärden returnerar en lista över alla hörnpunkter som är direkt anslutna till toppunktet x. Värdet och positionen för en post i en matris indikerar anslutningen av en kant.
remove_vertex (G, x)
Denna åtgärd tar bort ett toppunkt, x från ett diagram. Om toppunkten inte hade någon kant är det inga problem. Om toppunktet hade länkar bör länkarna (kanterna) också tas bort. Värdet och positionen för en post i en matris indikerar närvaron av ett visst toppunkt. Om ett toppunkt tas bort måste matrisen justeras om.
add_vertex (G, x)
Detta lägger till ett toppunkt, x utan att lägga till kanter, eller ersätter ett toppunkt som hade kanter men hade tagits bort. Värdet och positionen för en post i en matris indikerar närvaron av ett visst toppunkt. Om ett toppunkt läggs till måste matrisen justeras om.
add_edge (G, x, y)
Denna operation lägger till en ny kant mellan vertex x och vertex y om kanten inte var där. Värdet och positionen för en post i en matris indikerar närvaron av en viss kant. Om en kant läggs till måste matrisen justeras om.
remove_edge (G, x, y)
Denna operation skulle ta bort kanten mellan vertex x och vertex y om kanten fanns där. Värdet och positionen för en post i en matris indikerar närvaron av en viss kant. Om en kant tas bort måste matrisen justeras om.
get_vertex_value (G, x)
Denna åtgärd returnerar värdet, v associerat med toppunkten, x. För att uppnå detta behöver du en kraftuppsättning av delmängder för vertex-etiketter och deras värden.
set_vertex_value (G, x, v)
Denna operation ger ett nytt värde, v för värdet associerat med toppunkten, x. För att uppnå detta behöver du en kraftuppsättning av delmängder för vertex-etiketter och deras värden.
Vissa grafer associerar också värden till sina kanter. Sådana grafer behöver följande ytterligare operationer:
get_edge_value (G, x, y)
Denna operation returnerar värdet, v associerat med kanten, (x, y). För att uppnå detta behöver du en kraftuppsättning av delmängder för kanter och deras värden.
set_edge_value (G, x, y, v)
Denna operation ger ett nytt värde, v för värdet associerat med kanten, (x, y). För att uppnå detta behöver du en kraftuppsättning av delmängder för kanter och deras värden.
Slutsats
En graf är en uppsättning hörn som är förbundna med kanter. En graf kan inte riktas eller riktas. Kanterna kan vara oriktade eller riktade. Slingor kan finnas eller saknas i ett diagram. Vad du bör lära dig nästa är inställning, effektinställning och multiset relaterade till grafer. Därefter bör du lära dig de olika typerna av grafer, till exempel en orienterad graf, vanlig graf, komplett graf, bipartitgraf, turneringsdiagram, flödesnätverksdiagram, etc.
Chrys
Om författaren
Chrysanthus Forcha
Upptäckter av matematikintegration från första principer och relaterade serier. Magisterexamen i teknisk utbildning, specialiserad på elektronik och datorprogramvara. BSc Elektronik. Jag har också kunskap och erfarenhet på magisternivå inom databehandling och telekommunikation. Av 20 000 författare var jag den 37: e bästa författaren på devarticles.com. Jag har arbetat inom dessa områden i mer än tio år.
Visa alla inlägg
