Instrueret graf
En rettet graf (eller digraph for kort ) er en (multi) graf, hvis kanter er tildelt en retning. Rettede kanter kaldes også buer , og i nogle kilder kaldes de blot kanter. En graf, hvor ingen kant er tildelt en retning, kaldes en urettet graf eller ikke -digraf .
Grundlæggende begreber
Formelt består en digraf af et sæt , hvis elementer kaldes knudepunkter , og et sæt ordnede par af knudepunkter .
Buen er indfaldende til toppunkterne og . I dette tilfælde siger de, at det er buens indledende toppunkt , og det er det endelige toppunkt .
En digraf opnået fra en simpel graf ved at orientere kanter kaldes rettet . I modsætning til sidstnævnte kan to hjørner i en vilkårlig simpel digraf forbindes med to forskelligt rettede buer.
En rettet komplet graf kaldes en turnering .
Forbindelse
En rute i en digraf er en vekslende sekvens af hjørner og buer af formen (hjørnepunkter kan gentages). Længden af ruten er antallet af buer i den.
En sti er en rute i en digraf uden gentagne buer, en simpel sti er uden gentagne hjørner. Hvis der er en sti fra et toppunkt til et andet, så kan det andet toppunkt nås fra det første.
En kontur er en lukket vej .
For en halv-rute fjernes begrænsningen af retningen af buerne , og en halv-sti og en halv -kontur defineres på samme måde .
En digraf er stærkt forbundet , eller simpelthen stærk , hvis alle dens hjørner er gensidigt tilgængelige ; en-vejs forbundet , eller blot en-vejs , hvis for to spidser mindst én er tilgængelig fra den anden; svagt forbundet , eller blot svagt , hvis man ignorerer retningen af buerne, opnås en forbundet (multi)graf;
Den maksimale stærke subgraf kaldes den stærke komponent ; den ensidede komponent og den svage komponent defineres ens.
Kondensationen af en digraf er en digraf , hvis toppunkter er stærke komponenter , og en bue i viser tilstedeværelsen af mindst en bue mellem de hjørner, der er inkluderet i de tilsvarende komponenter.
Yderligere definitioner
En rettet acyklisk graf eller klump er en konturløs digraf.
En rettet graf opnået fra en given en ved at ændre retningen af kanterne til det modsatte kaldes invers .
Billede og egenskaber for alle tre-node digrafer
Forklaring: S er svag, OC er ensidig, SS er stærk, H er en rettet graf, G er en hængekøje (acyklisk), T er en turnering
| 0 buer | 1 bue | 2 buer | 3 buer | 4 buer | 5 buer | 6 buer |
| tom, N, G | N, G | OS | CC | CC | fuld, CC | |
|---|---|---|---|---|---|---|
| OS, N, G | CC, N, T | CC | ||||
| C, N, G | OS, N, G, T | OS | ||||
| C, N, G | OS | OS |
Anvendelse af digrafer
Digrafer er meget brugt i programmering som en måde at beskrive systemer med komplekse forbindelser på. For eksempel er en af de vigtigste strukturer, der bruges i udviklingen af compilere og generelt til at repræsentere computerprogrammer, dataflowgrafen.
Binære relationer
En binær relation over en endelig bærer kan repræsenteres som en digraf . Antirefleksive relationer kan repræsenteres af en simpel digraf ; i det generelle tilfælde kræves en digraf med sløjfer. Hvis relationen er symmetrisk , så kan den repræsenteres af en urettet graf , og hvis den er antisymmetrisk, så ved en rettet graf .
Diverse
Suurballes algoritme er en algoritme til at finde to ikke-skærende (uden fælles kanter) stier i en rettet graf med ikke-negative vægte, sådan at begge stier forbinder det samme par af hjørner og har en minimum fælles længde.
Litteratur
- Harari F. Grafteori. — M .: URSS , 2003. — 300 s. — ISBN 5-354-00301-6 .
- Malm, Oistin . Grafteori. — M .: URSS , 2008. — 352 s. - ISBN 978-5-397-00044-4 .
- Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compilers : Principles, Techniques and Tools, 2. udgave = Compilers: Principles, Techniques and Tools. - 2. udg. - M .: "Williams" , 2008. - ISBN 978-5-8459-1349-4 .
| Datastrukturer | |
|---|---|
| Lister | |
| Træer | |
| Tæller | |
| Andet | |