| Graf | Består av noder og kanter |
| Løkke | En kant som går fra en node til seg selv i en pseudograf |
| Parallelle kanta | To eller flere kanter som forbinder de samme nodene i en multigraf |
| Enkel | multigraf eller pseudograf som hverken har løkker eller parallelle kanter. |
| Rettet graf | Ein graf der kantene er ordnede par ⟨u, v⟩ i stedet for mengder {u, v} |
| Tom graf/nullgraf | En graf uten kanter |
| Komplett graf | En enkel graf er komplett hvis hver node er nabo med enhver annen node |
| Komplement | Hvis G er en graf, er komplementet til G grafen som har de samme nodene som G, men hvor to noder er naboer hvis og bare hvis nodene ikke er naboer i G. Vi skriver G for komplementet til G. |
| Graden til ein node | antall kanter som ligger inntil noden
Graden til en node v er antall kanter som ligger inntil v. En løkke teller som to kanter. Med deg (v) mener vi graden til v. En node med grad 0 kalles isolert. |
| Isomorfi | La G og H være to grafer. En isomorfi fra G til H er en bijektiv funksjon f fra nodene i G til nodene i H som er slik at nodene u og v er naboer i G hvis og bare hvis nodene f(u) og f(v) er naboer i H.
En bijektiv funksjon f fra nodene I G og H som er slik at nodene u og v er naboer I G hvis og bare hvis nodene også er naboer i H. |
| Vandring/Tur | Vi kan skrive en vandring i en graf som en sekvens av noder og kanter ... (finn ut dette)/ En sekvens av noder |
| Sti | Dersom ingen noder forekommer meir enn ein gang under ei vandring
En sekvens av noder (og kan-
tene som forbinder dem) der in-
gen node gjentas |
| Vei | En sekvens av noder (og kan-
tene som forbinder dem) der in-
gen kant gjentast |
| Lukket vandring | En vandring hvor den første og siste noden sammenfaller kalles lukket |
| Krets | Ei lukka vandring der ingen kant forekommer meir enn ein gang |
| Sykel/lukka sti | Ein kan sjekke dette ved at ingen kant eller node førekomme meir enn ein gang under vandringa. Den må innehalde minst 3 noder. En graf uten sykler kalles asyklisk |
| Sammanhengande | En graf er sammenhengende hvis det finnes en sti mellom alle par av noder i grafen, det vil si at det er mulig å komme fra enhver node til enhver annen node ved å følge kantene |
| Eulervei | La G være en sammenhengende graf. En eulervei er en vandring som inneholder hver kant fra G nøyaktig én gang |
| Eulerkrets | En eulerkrets er en eulervei hvor den første og den siste noden sammenfaller
Ein kan sjekke dette ved å sjå om grafen er samanhengande og om kvar node har eit partal som grad |
| Eulersk | En sammenhengende graf som har en eulerkrets |
| Tre | Et tre er en sammenhengende, asyklisk graf (betyr utan sykkel). En node med grad én i et tre kalles en løvnode. En graf hvor alle komponentene er trær kalles en skog. |
| Hamiltonsti | La G være en sammenhengende graf. En hamiltonsti er en sti som inneholder hver node fra G nøyaktig én gang |
| Hamiltonsykel | En hamiltonsykel er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en hamiltonsykel kalles hamiltonsk. |
| Hamiltonsykel | En hamiltonsykel er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en hamiltonsykel kalles hamiltonsk. |
| Euler | inneholder hver kant nøyaktig en gang |
| Hamilton | inneholder hver node nøyaktig en gang |
| Hamilton | inneholder hver node nøyaktig en gang |
