Från Rilpedia

Du har inte behörighet att redigera denna sida, av följande anledning:

Du kan se och kopiera denna sidas källtext:

<noinclude>{{rpsv.from.wpsv}}</noinclude> : ''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 [[grafteori|riktad graf]] (även kallad [[grafteori|digraf]]). == Benämningar på speciella grafer == Inom [[grafteori]]n 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 == {{bidrag saknas}} == Beteckningar == {| |---- | ''V(G)'' | Mängden av alla hörn i grafen ''G'' |--- | ''E(G)'' | Mängden av alla kanter i grafen ''G'' |---- | ''&delta;(G)'' | Den minimala graden hos något hörn i grafen ''G'' |---- | ''&Delta;(G)'' | Den maximala graden hos något hörn i grafen ''G'' |---- | ''K_n'' | Komplett graf av ordning ''n'' |---- | ''K_n,m | Komplett bipartit graf med ''n'' respektive ''m'' hörn i varje del |---- | <math>\omega_G</math> | Antalet [[komponent_(grafteori)|komponenter]] i <math>G</math>. |---- |} [[Kategori:Grafteori]] [[bg:Граф (математика)]] [[bn:গ্রাফ (গণিত)]] [[ca:Graf]] [[cs:Graf (teorie grafů)]] [[de:Graph (Graphentheorie)]] [[en:Graph (mathematics)]] [[eo:Grafeo]] [[es:Grafo]] [[et:Graaf]] [[fr:Graphe simple]] [[hu:Gráf]] [[id:Graf (matematika)]] [[it:Grafo]] [[ko:그래프]] [[lt:Grafas (matematika)]] [[ml:ആരേഖം]] [[pl:Graf (matematyka)]] [[pms:Graf]] [[pt:Grafo]] [[ro:Graf]] [[ru:Граф (математика)]] [[sk:Graf (matematika)]] [[th:กราฟ (คณิตศาสตร์)]] [[uk:Граф (математика)]] [[ur:مخطط (ریاضی)]] [[zh:图]]

Tillbaka till Graf (grafteori).