Graf (grafteori)
Från Rilpedia
- Se graf för andra betydelser.
En graf G är ett par (V,E) där V är en mängd av hörn (även kallade noder eller punkter) och E en mängd av kanter (även kallade bågar), där man normalt använder uv för att beteckna en kant. I en ändlig graf är E och V ändliga. För ändliga grafer så är grafens ordning antalet hörn och grafens storlek antalet kanter.
De vanligaste graferna har oriktade kanter. Det betyder att en kant från u till v är samma sak som en kant från v till u. Man kan då beskriva samma kant på två sätt: uv och vu. Mer teoretiskt så innehåller kantmängden E delmängder av V med två element.
Det finns också riktade grafer. Då är en kant från u till v inte detsamma som en kant från v till u. Alltså är uv och vu olika kanter. När man ritar riktade grafer brukar man använda pilar för att markera riktningen. Kantmängden E består av par av element från mängden V. Se riktad graf (även kallad digraf).
Benämningar på speciella grafer
Inom grafteorin använder man ett antal benämningar på grafer av särskilt intresse:
- I en komplett graf finns det en kant mellan varje par av hörn
- I en sammanhängande graf finns det minst en väg mellan varje par av hörn
- I ett träd finns det exakt en väg mellan varje par av noder
- I en skog finns det som mest en väg mellan varje par av noder
- I en bipartit graf kan man dela upp noderna i två grupper, så att varje kant förbinder en nod i ena gruppen med en nod i den andra.
Egenskaper hos grafer
 |
Detta korta avsnitt behöver utökas. |
Beteckningar
| V(G) | Mängden av alla hörn i grafen G |
| E(G) | Mängden av alla kanter i grafen G |
| δ(G) | Den minimala graden hos något hörn i grafen G |
| Δ(G) | Den maximala graden hos något hörn i grafen G |
| Kn | Komplett graf av ordning n |
| Kn,m | Komplett bipartit graf med n respektive m hörn i varje del |
| ωG | Antalet komponenter i G. |
