Regissert graf - Directed graph
I matematikk , og mer spesifikt i grafteori , er en rettet graf (eller digraf ) en graf som består av et sett med hjørner forbundet med rettet kant, ofte kalt buer .
Definisjon
Formelt sett er en rettet graf et ordnet par G = ( V , A ) hvor
- V er et sett hvis elementer kalles hjørner , noder eller punkter ;
- A er et sett med ordnede par av hjørner, kalt buer , rettet kant (noen ganger bare kanter med tilsvarende sett kalt E i stedet for A ), piler eller rettet linjer .
Den skiller seg fra en vanlig eller ikke-rettet graf ved at den sistnevnte er definert i form av uordnede par av hjørner, som vanligvis kalles kanter , lenker eller linjer .
Den nevnte definisjonen tillater ikke at en rettet graf har flere piler med samme kilde- og målnoder, men noen forfattere anser en bredere definisjon som gjør at dirigerte grafer kan ha slike flere buer (nemlig at de lar buesettet være et flersett ) . Mer spesifikt adresseres disse enhetene som rettet multigrafi (eller multidiagram ).
På den annen side tillater den nevnte definisjonen at en rettet graf har sløyfer (det vil si buer som direkte forbinder noder med seg selv), men noen forfattere anser en smalere definisjon som ikke tillater at rettet grafer har sløyfer. Mer spesifikt adresseres rettet grafer uten sløyfer som enkle rettet grafer , mens rettet grafer med sløyfer adresseres som sløyfediagrammer (se avsnitt Typer av rettet grafer ).
Typer av rettet grafer
Underklasser
- Symmetrisk rettet grafer er rettet grafer der alle kanter er toveis (det vil si at for hver pil som tilhører digrafen, tilhører også den tilsvarende omvendte pilen den).
-
Enkle dirigerte grafer er dirigerte grafer som ikke har noen sløyfer (piler som kobler toppunktene direkte til seg selv) og ingen flere piler med samme kilde- og målnoder. Som allerede introdusert adresseres enheten vanligvis som rettet multigraf i tilfelle flere piler . Noen forfattere beskriver digrafer med sløyfer som loop-digrafer .
- Komplette rettet grafer er enkle rettet grafer der hvert par av hjørner er sammenføyd av et symmetrisk par rettet buer (det tilsvarer en ikke-rettet komplett graf med kantene erstattet av par med omvendte buer). Det følger at en fullstendig digraf er symmetrisk.
- Halvkomplette flerdelte grafer er enkle grafer der toppunkt settet er delt inn i partitt sett slik at det for hvert par av hjørner x og y i forskjellige partitt sett er det en bue mellom x og y . Merk at det kan være en bue mellom x og y eller to buer i motsatt retning.
- Halvkomplette graver er enkle grafer der det er en bue mellom hvert par av toppunktene. Hver semikomplette digraf er en semikomplett graf med flere partier, hvor antall hjørner er lik antall partitt-sett.
- Kva-transitive graver er enkle grafer der for hver trippel x , y , z med forskjellige hjørner med buer fra x til y og fra y til z , er det en bue mellom x og z . Merk at det bare kan være en bue mellom x og z eller to buer i motsatt retning. En halvfull graf er en kvasi-transitiv graf. Det er utvidelser av kvasi-transitive digrafer kalt k- kvasi-transitive digrafer.
-
Orienterte grafer er dirigerte grafer som ikke har noen toveis kanter (dvs. høyst en av ( x , y ) og ( y , x ) kan være piler i grafen). Det følger at en rettet graf er en orientert graf hvis og bare hvis den ikke har noen 2-syklus .
- Turneringer er orienterte grafer oppnådd ved å velge en retning for hver kant i ikke-rettede komplette grafer . Legg merke til at en turnering er en halvfull graf.
-
Riktede asykliske grafer (DAGer) er dirigerte grafer uten rettet syklus .
- Multitrees er DAG-er der ingen to distribuerte ruter fra et enkelt start-toppunkt møtes tilbake i samme endepunkt.
-
Orienterte trær eller polytrees er DAG-er dannet ved å orientere kantene på ikke-rettet asykliske grafer.
- Rotede trær er orienterte trær der alle kantene av det underliggende ikke-rettede treet er rettet enten fra eller mot roten (de kalleshenholdsvis ut-trær og inn-trær .
Graver med supplerende egenskaper
-
Vekterte rettet grafer (også kjent som rettet nettverk ) er (enkle) rettet grafer med vekter tilordnet pilene, på samme måte som vektede grafer (som også er kjent som ikke-rettet nettverk eller vektede nettverk ).
- Strømningsnettverk er vektet rettet graf der to noder skilles ut, en kilde og en vask .
-
Forankrede rettede grafer (også kjent som flytgrafer ) er grafer der et toppunkt har blitt skilt ut som roten.
- Kontrollflytgrafer er forankrede
Grunnleggende terminologi
En bue ( x , y ) anses å være rettet fra x til y ; y kalles hodet og x kalles buens hale ; y sies å være en direkte etterfølger av x og x sies å være en direkte forgjenger av y . Hvis en sti fører fra x til y , sies y å være en etterfølger av x og nås fra x , og x sies å være en forgjenger av y . Buen ( y , x ) kalles den omvendte buen til ( x , y ) .
Den naboskapsmatrisen av en multidigraph med løkker er heltall-verdi matrise med rader og kolonner svarende til hjørnene, hvor en nondiagonal inngangs et ij er antall buer fra topp-punkt i til topp-punkt j , og den diagonal en ii er antallet av løkker i toppunktet i . Tilstøtningsmatrisen til en rettet graf er unik opp til identisk permutasjon av rader og kolonner.
En annen matrisepresentasjon for en rettet graf er dens forekomstmatrise .
Se retning for flere definisjoner.
Indegree og outdegree
For et toppunkt kalles antall hodeender ved siden av et toppunkt indegraden til toppunktet, og antall haleavslutninger ved siden av et toppunkt er dets utegrad (kalt forgreningsfaktor i trær).
La G = ( V , A ) og v ∈ V . Indegraden til v er betegnet deg - ( v ) og dens utegrad er betegnet deg + ( v ).
Et toppunkt med deg - ( v ) = 0 kalles en kilde , da det er opprinnelsen til hver av de kommende buene. Tilsvarende kalles et toppunkt med deg + ( v ) = 0 en vask , siden det er slutten på hver av sine innkommende buer.
Den grad Summen formel fastslår at for en rettet graf,
Hvis for hvert toppunkt v ∈ V , deg + ( v ) = deg - ( v ) , kalles grafen en balansert rettet graf .
Gradsekvens
Gradsekvensen til en rettet graf er listen over dets utegrader og utraderte par; for eksemplet ovenfor har vi gradssekvens ((2, 0), (2, 2), (0, 2), (1, 1)). Gradsekvensen er en rettet graf invariant, så isomorfe rettet grafer har samme gradssekvens. Imidlertid identifiserer gradssekvensen generelt ikke en rettet graf unikt; i noen tilfeller har ikke-isomorfe grafer samme gradssekvens.
Det dirigerte grafrealiseringsproblemet er problemet med å finne en rettet graf med gradssekvensen en gitt sekvens av positive heltallspar . (Etterfølgende par med nuller kan ignoreres siden de realiseres trivielt ved å legge til et passende antall isolerte hjørner til den rettet grafen.) En sekvens som er gradssekvensen til en eller annen rettet graf, dvs. for hvilken det rettet grafrealiseringsproblemet har en løsning , kalles en rettet grafisk eller rettet grafisk sekvens. Dette problemet kan enten løses av Kleitman – Wang-algoritmen eller av Fulkerson – Chen – Anstee-teoremet .
Rettet grafforbindelse
En rettet graf er svakt forbundet (eller bare koblet sammen ) hvis den ikke-rettede underliggende grafen oppnådd ved å erstatte alle rettet kantene av grafen med ikke-rettet kanter er en sammenhengende graf .
En rettet graf er sterkt koblet eller sterk hvis den inneholder en rettet bane fra x til y (og fra y til x ) for hvert par av hjørner ( x , y ) . De sterke komponentene er de maksimalt sterkt koblede subgrafene.
En koblet rotfestet graf (eller flytgraf ) er en der det eksisterer en rettet bane til hvert toppunkt fra et fremtredende rotpunkt .
Se også
- Binær forhold
- Coates-graf
- DRAKON flytskjema
- Flytskjema
- Ordliste over grafteori
- Grafteori
- Graf (abstrakt datatype)
- Nettverksteori
- Orientering
- Forhåndsbestille
- Topologisk sortering
- Transponere graf
- Vertikal begrensningsgraf
- Kuleformet sett
Merknader
Referanser
-
Bang-Jensen, Jørgen; Gutin, Gregory (2000), Digraphs: Theory, Algorithms and Applications , Springer , ISBN 1-85233-268-9
(den korrigerte 1. utgaven av 2007 er nå fritt tilgjengelig på forfatternes side; den andre utgaven dukket opp i 2009 ISBN 1-84800-997-6 ). - Bang-Jensen, Jørgen; Gutin, Gregory (2018), Classes of Directed Graphs , Springer , ISBN 3319718401.
- Bondy, John Adrian ; Murty, USR (1976), Grafteori med applikasjoner , Nord-Holland, ISBN 0-444-19451-7.
- Diestel, Reinhard (2005), Graph Theory (3. utg.), Springer , ISBN 3-540-26182-6 (den elektroniske 3. utgaven er fritt tilgjengelig på forfatterens nettsted).
- Harary, Frank ; Norman, Robert Z .; Cartwright, Dorwin (1965), Structural Models: An Introduction to Theory of Directed Graphs , New York: Wiley.
- Antall rettet grafer (eller rettet grafer) med n noder fra On-Line Encyclopedia of Integer Sequences