Phenquestions
En knude i en graf kaldes et toppunkt (flertal - hjørner). Det kaldes undertiden stadig en knude; det kan også kaldes et punkt. Et link i en graf kaldes en kant. Det kaldes undertiden stadig et link; det kan også kaldes en linje.
Graf med mange funktioner
Denne figur viser en graf med mange funktioner:
Cirklerne (diske) er hjørner. Enhver lige linje eller buet linje eller løkke er en kant.
Grafens funktioner
Hvirvel
Et toppunkt er et objekt. Det kan være et hus; det kan være en person; det kan være et abstrakt substantiv; det kan være ethvert objekt, du kan tænke på.
Edge
En kant er en forbindelse (relation) mellem to hjørner; forbindelsen kan være abstrakt.
Sløjfe
En sløjfe er en kant, der forbinder et toppunkt med sig selv.
Pilkanten
Overvej to personer: John og Peter. Hvis John låner Peter $ 100, og hvis John og Peter er hjørner, så vil udlåningskanten pege mod Peter. Hvis begge partnere glemmer, at Peter skylder John, og Peter låner John $ 100, vil en pilespids i den anden ende af samme kant pege mod John. Hvis Peter kun lånte $ 75 til John og ikke $ 100, ville en anden kant forbinde Peter med John. Denne anden kant vil have sin pilespids, der peger mod John. I det andet tilfælde er der to kanter med en pilespids hver, der peger i modsatte retninger.
Hovedpunktet, som en kant peger mod, er et hovedhovedpunkt for den kant. Hovedet, hvorfra en kant forlader, er et halehoved.
Utilsigtet hændelse
En kant forbinder to hjørner. Kanten siges at være hændende i begge hjørner. Kanten behøver ikke at have en pilespids. De to hjørner er kendt som slutpunkterne på kanten. Det er muligt at have en graf, hvor et toppunkt ikke hører til nogen kant, men det vil ikke blive taget i betragtning i denne vejledning.
Udirigeret graf
En kant kan være en pil, eller den kan ikke. En graf, hvor ingen kant er en pil, er en ikke-rettet graf. En kant kan repræsenteres af en lige linje eller en kurve eller en sløjfe.
Regisseret graf
En graf, hvor hver kant er en pil (retning) er en rettet graf. En pilkant kan repræsenteres af en lige linje med en pilehoved eller en kurve med en pilehoved eller en sløjfe med en pilehoved.
Fraværet af en retning på kanten af en ikke-rettet graf betyder, at hver kant af den ikke-rettet graf er tovejs.
Grad af en vertex
Antallet af kanter, der rammer et toppunkt, er graden af toppunktet. En sløjfe har to forekomster på et toppunkt, så en sløjfe tælles to gange.
Rækkefølge af en graf
Rækkefølgen af en graf er antallet af hjørner i grafen.
Multigraf
En multigraf er en graf, hvor der for nogle par af hjørner er mere end en kant. En ikke-rettet multigraf er en sådan graf, hvor kanterne ikke har retninger (er ikke pile). En rettet multigraf er en, hvor hver kant er en pil, og for par af hjørner, der har mere end en pil, er det ene toppunkt halen på disse pile, og det andet toppunkt er hovedet på de samme pile. Følgende diagram viser en ustyret multigraf:
Mere end en kant (i.e. flere kanter) til et par hjørner kaldes også parallelle kanter.
Kogger
En kogger er et multigraf, der tillader sløjfer (en eller flere sløjfer). Nogle multigrafier tillader ikke sløjfer.
Enkel graf
En simpel graf er en graf, hvor ingen to par af hjørner har flere kanter. Sløjfer er ikke tilladt i en simpel graf.
Tom graf
En tom graf er en graf uden hjørner og så ingen kanter.
Blandet graf
En blandet graf er en graf, hvor nogle kanter er pile, og andre ikke er; med andre ord: nogle kanter har retninger, og andre er ikke rettet.
Vægtet graf
Det er muligt at have en graf, hvor et tal, kendt som vægt, tildeles hver kant. Nogle kanter har samme nummer, men tallene er generelt forskellige. En sådan graf kaldes en vægtet graf. Tallene for en bestemt graf kan repræsentere længder eller omkostninger (priser) eller størrelsesorden af en slags, afhængigt af problemet.
Indegree og Outdegree
Ordforrådet, indegraden og udgravningen gælder kun for en rettet graf. Grafen kan måske ikke være en multigraf. Grafen har måske ikke sløjfer.
Antallet af pilespidser, der er forbundet med et toppunkt, er indegraden for dette toppunkt. En pil med en enkelt pilespids har en hovedende og en haleende. Antallet af haler, der er forbundet med et toppunkt, er udpegningen af det toppunkt.
Bemærk: En graf med flere kanter til parret af hjørner, hvor de flere kanter er i modsat retning, er ikke behandlet i denne vejledning.
Software repræsentation af en graf
En graf kan vises i software, som den er tegnet på diagrammet. En graf kan også repræsenteres i software af en matematisk matrix (todimensionalt array). En af sådanne matricer kaldes adjacency matrix.
Adjacency Matrix
En adjacency matrix er en firkantet matrix. Overskrifterne for rækkerne er alle hjørner, skrevet i stigende rækkefølge. Overskrifterne for kolonnerne er stadig de samme hjørner, skrevet i stigende rækkefølge. Optælling af rækker eller kolonner i en matrix begynder fra 1 og ikke nul som med arrays. Når der identificeres et element i en matrix, skrives række nummer først før kolonnenummeret.
For en ikke-rettet graf er hver post (element) i adjacency matrix antallet af kanter, der forbinder de to tilsvarende hjørner. En sløjfe skal tælles to gange. For en rettet graf er hver post i tilpasningsmatricen enten antallet af kanter, der forlader et rækkehoved og indtaster det tilsvarende søjlepunkt, eller er antallet af kanter, der forlader et søjlepunkt og indtaster det tilsvarende rækkehoved. Valget er programmørens. I denne situation (i begge tilfælde) skal der stadig tælles en løkke én gang.
Bemærk: En graf er et diagram er en datastruktur i sig selv. En nærhedsmatrix er også en datastruktur i sig selv.
Ustyret matrix til graf og tilstødende karakter
Følgende diagrammer viser en ikke-rettet graf og den tilsvarende nærhedsmatrix:
Den førende diagonal i en matrix er diagonalen fra øverst til venstre til nederst til højre. En ikke-rettet matrix er symmetrisk omkring den førende diagonal. Matrixindgangen for række A og kolonne C er 1, hvilket betyder, at der er en kant, der forbinder toppunkt A og toppunkt C. Matrixindgangen for række C og kolonne B er 3, hvilket betyder at der er 3 kanter, der forbinder toppunkt C og toppunkt B. De andre poster forklares på samme måde.
Summen af posterne for en række giver antallet af kanter (grad) for det tilsvarende toppunkt. Summen af posterne for række A er 2, hvilket betyder at to kanter er forbundet med toppunkt A. Summen af posterne for række B er 6, hvilket betyder, at 6 kanter er forbundet med toppunkt B. Resten af posterne forklares på samme måde.
Regisseret graf og tilstødende matrix
De følgende diagrammer viser en rettet graf og den tilsvarende nærhedsmatrix:
Nærhedsmatrixen for en rettet graf er ikke nødvendigvis symmetrisk omkring den førende diagonal. Matrixindgangen for række A og kolonne C er 1, hvilket betyder at den ene kant forlader fra toppunkt A til toppunkt C. Matrixindgangen for række C og kolonne B er 3, hvilket betyder, at 3 kanter går fra toppunkt C til toppunkt B. De andre poster forklares på samme måde.
Summen af posterne for en kolonne giver indegraden for (kolonne) toppunktet. Summen af posterne for en række giver outgrad for (række) toppunktet. Summen af posterne for kolonne A er 1, hvilket betyder at den ene kant er rettet mod toppunkt A. Summen af posterne for række B er 2, hvilket betyder at 2 kanter forlader toppunkt B. Resten af posterne forklares på samme måde.
Grafoperationer
En datastruktur, såsom en graf, består af et sæt dataværdier eller et sæt objekter plus forholdet mellem objekterne plus operationerne (funktionerne) mellem objekterne. Forholdet i en graf er angivet med kanterne. Dertil skal en graf mindst have følgende operationer:
tilstødende (G, x, y)
G betyder graf. Denne operation verificerer, om en kant forbinder toppunkt x og toppunkt y. Værdien og placeringen af en post i en matrix angiver forbindelsen af en kant (og dens type).
naboer (G, x)
Denne handling returnerer en liste over alle hjørner, der er direkte forbundet med toppunktet x. Værdien og placeringen af en post i en matrix angiver forbindelsen af en kant.
remove_vertex (G, x)
Denne handling fjerner et toppunkt, x fra en graf. Hvis toppunktet ikke havde nogen kant, er der ikke noget problem. Men hvis toppunktet havde links, så skulle linkene (kanterne) også fjernes. Værdien og placeringen af en post i en matrix angiver tilstedeværelsen af et bestemt toppunkt. Hvis et toppunkt fjernes, skal matrixen justeres igen.
add_vertex (G, x)
Dette tilføjer et toppunkt, x uden at tilføje kanter, eller erstatter et toppunkt, der havde kanter, men som var blevet fjernet. Værdien og placeringen af en post i en matrix angiver tilstedeværelsen af et bestemt toppunkt. Hvis der tilføjes et toppunkt, skal matrixen justeres igen.
add_edge (G, x, y)
Denne operation tilføjer en ny kant mellem toppunktet x og toppunktet y, hvis kanten ikke var der. Værdien og placeringen af en post i en matrix indikerer tilstedeværelsen af en bestemt kant. Hvis der tilføjes en kant, skal matrixen justeres igen.
remove_edge (G, x, y)
Denne operation fjerner kanten mellem toppunktet x og toppunktet y, hvis kanten var der. Værdien og placeringen af en post i en matrix angiver tilstedeværelsen af en bestemt kant. Hvis en kant fjernes, skal matrixen justeres igen.
get_vertex_value (G, x)
Denne operation returnerer værdien, v tilknyttet toppunktet, x. For at opnå dette har du brug for et styrkesæt med undergrupper til toppunktetiketter og deres værdier.
set_vertex_value (G, x, v)
Denne operation giver en ny værdi, v for den værdi, der er knyttet til toppunktet, x. For at opnå dette har du brug for et styrkesæt af delmængder til toppunktetiketter og deres værdier.
Nogle grafer knytter også værdier til deres kanter. Sådanne grafer har brug for følgende yderligere operationer:
get_edge_value (G, x, y)
Denne operation returnerer værdien, v tilknyttet kanten, (x, y). For at opnå dette har du brug for et styrkesæt af undergrupper til kanter og deres værdier.
set_edge_value (G, x, y, v)
Denne operation giver en ny værdi, v for den værdi, der er knyttet til kanten, (x, y). For at opnå dette har du brug for et styrkesæt af undergrupper til kanter og deres værdier.
Konklusion
En graf er et sæt hjørner forbundet med kanter. En graf kan ikke rettes eller rettes. Kanterne kan være ikke-retningsbestemte eller retningsbestemte. Sløjfer kan være til stede eller fraværende i en graf. Hvad du skal lære næste er indstillet, power set og multiset relateret til grafer. Derefter skal du lære de forskellige typer af grafer, såsom en orienteret graf, almindelig graf, komplet graf, bipartitgraf, turneringsgraf, flownetværksgraf osv.
Chrys
Om forfatteren
Chrysanthus Forcha
Opdageren af matematikintegration fra de første principper og relaterede serier. Kandidatgrad i teknisk uddannelse med speciale i elektronik og computersoftware. BSc Elektronik. Jeg har også viden og erfaring på kandidatniveau inden for computing og telekommunikation. Ud af 20.000 forfattere var jeg den 37. bedste forfatter på devarticles.com. Jeg har arbejdet inden for disse områder i mere end 10 år.
Vis alle indlæg
