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>[[Fil:Simple-bipartite-graph.svg|höger|miniatyr|200px|En bipartit graf partionerad i mängderna ''U'' och ''V''.]] En '''bipartit graf''' är en [[graf]] vars hörnmängd <math>V(G)</math> kan [[partition av en mängd|partitioneras]] som <math>V(G) = X \cup Y</math> där <math>X \cap Y = \emptyset</math> och där varje kant <math>e \in E(G)</math> kan skrivas på formen <math>e = \{x, y\}</math>, där <math>x \in X</math> och <math>y \in Y</math>. I så fall säges <math>G</math> ha ''bipartitionen'' (X,Y). Detta kan även uttryckas så att noderna i en bipartit graf kan indelas i två mängder, sådana att inga kanter går mellan två noder i samma mängd. == Egenskaper == *En graf är bipartit [[om och endast om]] den inte har några [[cykel (grafteori)|cykler]] av udda längd. *För bipartita grafer med icke-tomma kantmängder gäller att <math>\chi = 2</math>, där <math>\chi</math> är det [[kromatiskt_tal|kromatiska talet]]. *Varje bipartit graf är en [[perfekt graf]]. ==Exempel== Varje graf som inte har någon cykel av udda längd är bipartit. Exempel på grafer som uppfyller detta är [[träd_(graf)|träd]] och [[cyklisk graf|cykliska grafer]] med ett jämnt antal bågar. == Tillämpningar == Bipartita grafer har tillämpningar till områden utanför matematiken, till exempel inom schemaläggning. == Generalisering == En ''k-partit graf'' är en [[graf]] vars hörnmängd kan partitioneras som <math>V(G) = \bigcup _{k=0} ^{n-1} V_k</math>, och där varje kant <math>e \in E(G)</math> kan skrivas på formen <math>e = \{x, y\}</math>, där <math>x \in V_i</math> och <math>y \in V_j</math> och <math>i \neq j</math>. En graf har kromatiskt tal ''k'', om och endast om den är ,,k..-partit men inte (''k''-1)-partit. [[Kategori: grafteori]] [[ar:مخطط ثنائي]] [[cs:Bipartitní graf]] [[de:Bipartiter Graph]] [[en:Bipartite graph]] [[es:Grafo bipartito]] [[fa:گراف‌ دوبخشی]] [[fr:Graphe biparti]] [[he:גרף דו-צדדי]] [[hu:Páros gráf]] [[it:Grafo bipartito]] [[ja:2部グラフ]] [[ko:이분 그래프]] [[pl:Graf dwudzielny]] [[ru:Биграф]] [[th:กราฟสองส่วน]] [[vi:Đồ thị hai phía]] [[zh:二部圖]]

Tillbaka till Bipartit graf.