A Oriktade grafer : En graf där kanterna inte har någon riktning, dvs. kanterna inte har pilar som anger riktningen för korsningen. Exempel: Ett socialt nätverksdiagram där vänskap inte är riktgivande.

Regisserade grafer : En graf där kanterna har en riktning, dvs. kanterna har pilar som anger riktningen för korsningen. Exempel: En webbsidesgraf där länkar mellan sidor är riktade.

Viktade grafer: En graf där kanter har vikter eller kostnader förknippade med dem. Exempel: En vägnätsgraf där vikterna kan representera avståndet mellan två städer.

Oviktad graf s: En graf där kanter inte har några vikter eller kostnader förknippade med dem. Exempel: En graf för sociala nätverk där kanterna representerar vänskap.

Kompletta grafer: En graf där varje vertex är kopplat till vartannat vertex. Exempel: En turneringsgraf där varje spelare spelar mot alla andra spelare.

Tvådelade grafer: En graf där hörnen kan delas in i två disjunkta uppsättningar så att varje kant förbinder en vertex i en uppsättning med en vertex i den andra uppsättningen. Exempel: En arbetssökande graf där hörnen kan delas in i arbetssökande och lediga jobb.

Träd : En sammankopplad graf utan cykler. Exempel: Ett släktträd där varje person är kopplad till sina föräldrar.

Cyklar : En graf med minst en cykel. Exempel: En cykeldelningsgraf där cyklerna representerar vägarna som cyklarna tar.

Sparse grafer: En graf med relativt få kanter jämfört med antalet hörn. Exempel: En kemisk reaktionsgraf där varje hörn representerar en kemisk förening och varje kant representerar en reaktion mellan två föreningar.

Tät graf s: En graf med många kanter jämfört med antalet hörn. Exempel: En social nätverksgraf där varje hörn representerar en person och varje kant representerar en vänskap.

Typer av grafer:

1. Finita grafer

En graf sägs vara ändlig om den har ett ändligt antal hörn och ett ändligt antal kanter. En finit graf är en graf med ett begränsat antal hörn och kanter. Med andra ord är både antalet hörn och antalet kanter i en finit graf begränsade och kan räknas. Finita grafer används ofta för att modellera verkliga situationer, där det finns ett begränsat antal objekt och relationer mellan

2. Oändlig graf:

En graf sägs vara oändlig om den har ett oändligt antal hörn såväl som ett oändligt antal kanter.

3. Trivial graf:

En graf sägs vara trivial om en finit graf bara innehåller en vertex och ingen kant. En trivial graf är en graf med endast en vertex och inga kanter. Det är också känt som en singeltonsgraf eller en enda vertexgraf. En trivial graf är den enklaste typen av graf och används ofta som utgångspunkt för att bygga mer komplexa grafer. I grafteorin anses triviala grafer vara ett degenererat fall och studeras vanligtvis inte i detalj

solig deol ålder

4. Enkel graf:

En enkel graf är en graf som inte innehåller mer än en kant mellan paret av hörn. Ett enkelt järnvägsspår som förbinder olika städer är ett exempel på en enkel graf.

5. Multi Graph:

Varje graf som innehåller några parallella kanter men inte innehåller någon självslinga kallas en multigraf. Till exempel en vägkarta.

• Parallella kanter: Om två hörn är sammankopplade med mer än en kant kallas sådana kanter parallella kanter som är många rutter men en destination.
• Slinga: En kant på en graf som börjar från en vertex och slutar vid samma vertex kallas en loop eller en självloop.

6. Nulldiagram:

En graf av ordningen n och storlek noll är en graf där det bara finns isolerade hörn utan kanter som förbinder något par av hörn. En nollgraf är en graf utan kanter. Det är med andra ord en graf med bara hörn och inga kopplingar mellan dem. En nollgraf kan också hänvisas till som en kantlös graf, en isolerad graf eller en diskret graf

7. Komplett diagram:

En enkel graf med n hörn kallas en komplett graf om graden av varje vertex är n-1, det vill säga en vertex är fäst med n-1 kanter eller resten av hörnen i grafen. En komplett graf kallas även Full Graph.

8. Pseudograf:

En graf G med en självslinga och några flera kanter kallas en pseudograf. En pseudograf är en typ av graf som tillåter förekomsten av självslingor (kanter som förbinder en vertex till sig själv) och flera kanter (mer än en kant som förbinder två hörn). Däremot är en enkel graf en graf som inte tillåter loopar eller flera kanter.

9. Vanlig graf:

En enkel graf sägs vara regelbunden om alla hörn i graf G är lika stora. Alla kompletta grafer är regelbundna men vice versa är inte möjligt. En vanlig graf är en typ av oriktad graf där varje vertex har samma antal kanter eller grannar. Med andra ord, om en graf är regelbunden, har varje vertex samma grad.

10. Tvådelad graf:

En graf G = (V, E) sägs vara en tvådelad graf om dess vertexuppsättning V(G) kan delas upp i två icke-tomma disjunkta delmängder. V1(G) och V2(G) på ett sådant sätt att varje kant e av E(G) har en ände i V1(G) och en annan ände i V2(G). Partitionen V1 U V2 = V kallas Bipartite of G. Här i figuren: V1(G)={V5, V4, V3} och V2(G)={V1, V2}

11. Märkt graf:

Om hörn och kanter på en graf är märkta med namn, datum eller vikt kallas det en märkt graf. Det kallas också Weighted Graph.

12. Digraph Graph:

En graf G = (V, E) med en avbildning f så att varje kant avbildas på ett ordnat par av hörn (Vi, Vj) kallas en Digraph. Det kallas också Regisserad graf . Det ordnade paret (Vi, Vj) betyder en kant mellan Vi och Vj med en pil riktad från Vi till Vj. Här i figuren: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

13. Subgraf:

En graf G1 = (V1, E1) kallas en subgraf av en graf G(V, E) om V1(G) är en delmängd av V(G) och E1(G) är en delmängd av E(G) så att varje kant på G1 har samma ändpunkt som i G.

14. Ansluten eller frånkopplad graf:

Graf G sägs vara sammankopplad om något par av hörn (Vi, Vj) i en graf G kan nås från varandra. Eller en graf sägs vara ansluten om det finns minst en väg mellan varje par av hörn i graf G, annars är den frånkopplad. En nollgraf med n hörn är en frånkopplad graf som består av n komponenter. Varje komponent består av en vertex och ingen kant.

15. Cyklisk graf:

En graf G som består av n hörn och n> = 3 som är V1, V2, V3- – – – Vn och kanter (V1, V2), (V2, V3), (V3, V4)- – – – (Vn, V1) kallas cyklisk graf.

16. Typer av subgrafer:

• Vertex disjunkt subgraf: Varje två graf G1 = (V1, E1) och G2 = (V2, E2) sägs vara vertexdisjunktion av en graf G = (V, E) om V1(G1) skärningspunkten V2(G2) = noll. I figuren finns det ingen gemensam vertex mellan G1 och G2.
• Edge disjoint subgraf: En subgraf sägs vara kantdisjunken om E1(G1) skärningspunkt E2(G2) = noll. I figuren finns det ingen gemensam kant mellan G1 och G2.

Notera: Edge disjoint subgraf kan ha hörn gemensamma men en vertex disjunkt graf kan inte ha en gemensam kant, så vertex disjunction subgraf kommer alltid att vara en kant-disjunkt subgraf.

java listning

17. Spännande subgraf

Betrakta grafen G(V,E) som visas nedan. En spännande subgraf är en subgraf som innehåller alla hörn i den ursprungliga grafen G som är G'(V’,E’) spänner över om V’=V och E’ är en delmängd av E.

Så en av de spännande subgraferna kan vara som visas nedan G'(V',E'). Den har alla hörn på den ursprungliga grafen G och några av kanterna på G.

Detta är bara en av de många spännande subgraferna i graf G. Vi kan skapa olika andra spännande subgrafer genom olika kombinationer av kanter. Observera att om vi betraktar en graf G'(V’,E’) där V’=V och E’=E, så är graf G’ en spännande subgraf till graf G(V,E).

Fördelar med grafer:

1. Grafer kan användas för att modellera och analysera komplexa system och samband.
2. De är användbara för att visualisera och förstå data.
3. Grafalgoritmer används ofta inom datavetenskap och andra områden, såsom sociala nätverksanalyser, logistik och transport.
4. Grafer kan användas för att representera ett brett utbud av datatyper, inklusive sociala nätverk, vägnät och internet.

Nackdelar med grafer:

1. Stora grafer kan vara svåra att visualisera och analysera.
2. Grafalgoritmer kan vara beräkningsmässigt dyra, särskilt för stora grafer.
3. Tolkningen av grafresultat kan vara subjektiv och kan kräva domänspecifik kunskap.
4. Grafer kan vara känsliga för brus och extremvärden, vilket kan påverka analysresultatens noggrannhet.

Relaterad artikel: Tillämpningar, fördelar och nackdelar med Graph