A Ongerichte grafieken : Een grafiek waarin randen geen richting hebben, dat wil zeggen dat de randen geen pijlen hebben die de richting van de verplaatsing aangeven. Voorbeeld: een sociaal netwerkgrafiek waarin vriendschappen niet directioneel zijn.

Gerichte grafieken : Een grafiek waarin randen een richting hebben, d.w.z. de randen hebben pijlen die de richting van de verplaatsing aangeven. Voorbeeld: een webpaginagrafiek waarin links tussen pagina's directioneel zijn.

Gewogen grafieken: Een grafiek waarin aan randen gewichten of kosten zijn gekoppeld. Voorbeeld: een wegennetwerkgrafiek waarbij de gewichten de afstand tussen twee steden kunnen weergeven.

Ongewogen grafiek s: Een grafiek waarin randen geen gewichten of kosten met zich meebrengen. Voorbeeld: een sociaal netwerkgrafiek waarbij de randen vriendschappen vertegenwoordigen.

Volledige grafieken: Een grafiek waarin elk hoekpunt verbonden is met elk ander hoekpunt. Voorbeeld: een toernooigrafiek waarin elke speler tegen elke andere speler speelt.

Bipartiete grafieken: Een grafiek waarin de hoekpunten kunnen worden verdeeld in twee onsamenhangende sets, zodat elke rand een hoekpunt in de ene set verbindt met een hoekpunt in de andere set. Voorbeeld: een sollicitantengrafiek waarin de hoekpunten kunnen worden onderverdeeld in sollicitanten en vacatures.

Bomen : Een verbonden grafiek zonder cycli. Voorbeeld: een stamboom waarbij elke persoon verbonden is met zijn ouders.

Cycli : Een grafiek met minstens één cyclus. Voorbeeld: een grafiek voor het delen van fietsen waarbij de fietsen de routes vertegenwoordigen die de fietsen afleggen.

Schaarse grafieken: Een grafiek met relatief weinig randen vergeleken met het aantal hoekpunten. Voorbeeld: een chemische reactiegrafiek waarbij elk hoekpunt een chemische verbinding vertegenwoordigt en elke rand een reactie tussen twee verbindingen vertegenwoordigt.

Dichte grafiek s: Een grafiek met veel randen vergeleken met het aantal hoekpunten. Voorbeeld: een sociaal netwerkgrafiek waarbij elk hoekpunt een persoon vertegenwoordigt en elke rand een vriendschap vertegenwoordigt.

Soorten grafieken:

1. Eindige grafieken

Een graaf heet eindig als hij een eindig aantal hoekpunten en een eindig aantal randen heeft. Een eindige grafiek is een grafiek met een eindig aantal hoekpunten en randen. Met andere woorden, zowel het aantal hoekpunten als het aantal randen in een eindige grafiek is beperkt en kan worden geteld. Eindige grafieken worden vaak gebruikt om situaties uit de echte wereld te modelleren, waarbij er een beperkt aantal objecten en relaties tussen de objecten bestaat

2. Oneindige grafiek:

Er wordt gezegd dat een graaf oneindig is als hij zowel een oneindig aantal hoekpunten als een oneindig aantal randen heeft.

3. Triviale grafiek:

Er wordt gezegd dat een grafiek triviaal is als een eindige grafiek slechts één hoekpunt en geen rand bevat. Een triviale grafiek is een grafiek met slechts één hoekpunt en geen randen. Het is ook bekend als een singleton-grafiek of een enkele hoekpuntgrafiek. Een triviale grafiek is het eenvoudigste type grafiek en wordt vaak gebruikt als uitgangspunt voor het bouwen van complexere grafieken. In de grafentheorie worden triviale grafieken beschouwd als een gedegenereerd geval en worden ze doorgaans niet in detail bestudeerd

prioriteitswachtrij c++

4. Eenvoudige grafiek:

Een eenvoudige grafiek is een grafiek die niet meer dan één rand tussen het paar hoekpunten bevat. Een eenvoudige spoorlijn die verschillende steden met elkaar verbindt, is een voorbeeld van een eenvoudige grafiek.

5. Multigrafiek:

Elke grafiek die enkele parallelle randen bevat maar geen enkele zelflus bevat, wordt een multigraaf genoemd. Bijvoorbeeld een routekaart.

• Parallelle randen: Als twee hoekpunten met meer dan één rand zijn verbonden, worden dergelijke randen parallelle randen genoemd die veel routes zijn maar één bestemming.
• Lus: Een rand van een grafiek die begint bij een hoekpunt en eindigt bij hetzelfde hoekpunt, wordt een lus of een zelflus genoemd.

6. Nulgrafiek:

Een grafiek van orde n en grootte nul is een grafiek waarin er alleen geïsoleerde hoekpunten zijn zonder randen die een paar hoekpunten met elkaar verbinden. Een nulgrafiek is een grafiek zonder randen. Met andere woorden, het is een grafiek met alleen hoekpunten en geen verbindingen daartussen. Een nulgrafiek kan ook een randloze grafiek, een geïsoleerde grafiek of een discrete grafiek worden genoemd

7. Volledige grafiek:

Een eenvoudige grafiek met n hoekpunten wordt een volledige grafiek genoemd als de graad van elk hoekpunt n-1 is, dat wil zeggen dat één hoekpunt is verbonden met n-1 randen of de rest van de hoekpunten in de grafiek. Een volledige grafiek wordt ook wel Volledige grafiek genoemd.

8. Pseudografiek:

Een grafiek G met een zelflus en enkele meerdere randen wordt een pseudografiek genoemd. Een pseudograaf is een type grafiek dat het bestaan ​​mogelijk maakt van zelflussen (randen die een hoekpunt met zichzelf verbinden) en meerdere randen (meer dan één rand die twee hoekpunten verbindt). Een eenvoudige grafiek is daarentegen een grafiek die geen lussen of meerdere randen toestaat.

9. Regelmatige grafiek:

Van een eenvoudige grafiek wordt gezegd dat deze regulier is als alle hoekpunten van grafiek G van gelijke graad zijn. Alle volledige grafieken zijn regelmatig, maar omgekeerd is niet mogelijk. Een gewone grafiek is een soort ongerichte grafiek waarbij elk hoekpunt hetzelfde aantal randen of buren heeft. Met andere woorden: als een grafiek regelmatig is, heeft elk hoekpunt dezelfde graad.

10. Bipartiete grafiek:

Er wordt gezegd dat een grafiek G = (V, E) een bipartiete grafiek is als de hoekpuntverzameling V(G) kan worden opgedeeld in twee niet-lege disjuncte deelverzamelingen. V1(G) en V2(G) zodanig dat elke rand e van E(G) één uiteinde heeft in V1(G) en een ander uiteinde in V2(G). De partitie V1 U V2 = V wordt Bipartiet van G genoemd. Hier in de figuur: V1(G)={V5, V4, V3} en V2(G)={V1, V2}

11. Gelabelde grafiek:

Als de hoekpunten en randen van een grafiek zijn voorzien van een naam, datum of gewicht, wordt dit een gelabelde grafiek genoemd. Het wordt ook wel gewogen grafiek genoemd.

12. Digraph-grafiek:

Een grafiek G = (V, E) met een afbeelding f zodat elke rand op een geordend paar hoekpunten (Vi, Vj) wordt afgebeeld, wordt een Digraph genoemd. Het wordt ook wel genoemd Gerichte grafiek . Het geordende paar (Vi, Vj) betekent een rand tussen Vi en Vj met een pijl gericht van Vi naar Vj. Hier in de figuur: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

13. Subgrafiek:

Een grafiek G1 = (V1, E1) wordt een subgraaf van een grafiek G(V, E) genoemd als V1(G) een deelverzameling is van V(G) en E1(G) een deelverzameling van E(G) is, zodat elke rand van G1 heeft dezelfde eindhoekpunten als in G.

14. Verbonden of niet-verbonden grafiek:

Er wordt gezegd dat grafiek G verbonden is als een paar hoekpunten (Vi, Vj) van een grafiek G van elkaar bereikbaar zijn. Of er wordt gezegd dat een graaf verbonden is als er ten minste één pad bestaat tussen elk paar hoekpunten in grafiek G, anders is deze ontkoppeld. Een nulgrafiek met n hoekpunten is een losgekoppelde grafiek die uit n componenten bestaat. Elke component bestaat uit één hoekpunt en geen rand.

15. Cyclische grafiek:

Een grafiek G bestaande uit n hoekpunten en n> = 3, dat wil zeggen V1, V2, V3- – – – Vn en randen (V1, V2), (V2, V3), (V3, V4)- – – – (Vn, V1) worden cyclische grafiek genoemd.

if en else in bash

16. Soorten subgrafieken:

• Vertex disjuncte subgraaf: Van elke twee grafieken G1 = (V1, E1) en G2 = (V2, E2) wordt gezegd dat ze een disjunct punt zijn van een grafiek G = (V, E) als V1(G1) snijpunt V2(G2) = nul. In de figuur is er geen gemeenschappelijk hoekpunt tussen G1 en G2.
• Rand disjuncte subgraaf: Er wordt gezegd dat een subgraaf rand-disjunct is als snijpunt E1(G1) E2(G2) = nul. In de figuur is er geen gemeenschappelijke flank tussen G1 en G2.

Opmerking: De disjuncte subgraaf van de rand kan hoekpunten gemeenschappelijk hebben, maar een disjuncte hoekpuntgrafiek kan geen gemeenschappelijke rand hebben, dus de disjuncte subgraaf van het hoekpunt zal altijd een disjuncte subgraaf van de rand zijn.

17. Subgrafiek overspannen

Beschouw de grafiek G(V,E) zoals hieronder weergegeven. Een opspannende subgraaf is een subgraaf die alle hoekpunten bevat van de oorspronkelijke graaf G, dat wil zeggen dat G'(V’,E’) zich uitstrekt als V’=V en E’ een deelverzameling van E is.

Een van de overspannende subgrafieken kan dus zijn zoals weergegeven onder G'(V’,E’). Het heeft alle hoekpunten van de oorspronkelijke grafiek G en enkele randen van G.

Dit is slechts één van de vele overspannende subgrafen van grafiek G. We kunnen diverse andere overspannende subgrafen creëren door verschillende combinaties van randen. Merk op dat als we een grafiek G'(V’,E’) beschouwen waarin V’=V en E’=E, grafiek G’ een overspannende subgraaf is van grafiek G(V,E).

Voordelen van grafieken:

1. Grafieken kunnen worden gebruikt om complexe systemen en relaties te modelleren en analyseren.
2. Ze zijn nuttig voor het visualiseren en begrijpen van gegevens.
3. Grafiekalgoritmen worden veel gebruikt in de informatica en op andere gebieden, zoals de analyse van sociale netwerken, logistiek en transport.
4. Grafieken kunnen worden gebruikt om een ​​breed scala aan gegevenstypen weer te geven, waaronder sociale netwerken, wegennetwerken en internet.

Nadelen van grafieken:

1. Grote grafieken kunnen moeilijk te visualiseren en te analyseren zijn.
2. Grafiekalgoritmen kunnen rekentechnisch duur zijn, vooral voor grote grafieken.
3. De interpretatie van grafiekresultaten kan subjectief zijn en vereist mogelijk domeinspecifieke kennis.
4. Grafieken kunnen gevoelig zijn voor ruis en uitschieters, wat van invloed kan zijn op de nauwkeurigheid van de analyseresultaten.

Gerelateerd artikel: Toepassingen, voordelen en nadelen van Graph