Plena dukolora grafeo

Plena dukolora grafeo
Plia nomo	Dukliko
Plena dukolora grafeo kun m=3, n=2
Dukolora grafeo • plena plurparta grafo • biregular graph • kografo • chordal bipartite graph • graca grafo • unike kolorebla grafo
Verticoj	m+n
Lateroj	mn
Aŭtomorfioj	2m!n! se m=n, m!n! se m≠n

En grafeoteorio, plena dukolora grafeo aŭ dukliko estas speciala tipo de dukolora grafeo, ĉe kiu ĉiu vertico de la unua aro estas koneksa al ĉiu vertico de la dua aro.

Tiel, plena dukolora grafeo G = (V₁ + V₂, E) estas dukolora grafeo tia ke por ĉiuj du verticoj $v_{1}\in V_{1}$ kaj $v_{2}\in V_{2}$, estas eĝo v₁v₂ en E.

Pro tio ke la grafeo estas dukolora, por ĉiuj du verticoj $v_{1}\in V_{1}$ kaj $v_{2}\in V_{1}$, eĝo v₁v₂ ne estu en G; same por $v_{1}\in V_{2}$ kaj $v_{2}\in V_{2}$.

Plena dukolora grafeo kies dispartigoj havas vertic-nombrojn |V₁|=m kaj |V₂|=n estas skribata kiel K_{{m, n}}.

Por ĉiu k, K_{{1, k}} nomiĝas stelgrafeo.

Ekzemploj

K1,3

K2,3

K3,3

La stelgrafeoj K_1,3, K_1,4, K_1,5, kaj K_1,6.

La artikolo estas parto de serio pri grafeoteorio.

Plej gravaj terminoj grafeo arbo subgrafeo ciklo kliko grado de vertico grado de grafeo Elektitaj klasoj de grafeoj plena grafeo plena dukolora grafeo kohera grafeo arbo grafeo dudividebla Fenda grafeo regula grafeo grafeo de Euler grafeo de Hamilton grafeo senrelifa pli... Grafeaj algoritmoj A* Bellman-Ford Dijkstry Fleury Floyd-Warshall Johnson Kruskal Prim traserĉado de grafeo – en larĝeco – en profundo plej proksima najbaro Problemoj prezentataj kiel grafeaj problemo de vojaĝisto problemo de ĉina leteristo problemo de marŝrutigado problemo de kunigado de geedzoj Aliaj kodo de Gray diagramo de Hasse kodo de Prüfer Reprezentado de grafeo Glosaro de grafeoteorio

Propraĵoj

• Por dukolora grafeo, trovado de ĝia plena dukolora subgrafeo K_{{m, n}} kun maksimuma kvanto de lateroj mn estas NP-plena problemo.
• Ebena grafeo ne povas enhavi K_{3,3} kiel minoro; ekstere ebena grafeo ne povas enhavi K_{3,2} kiel minoro (ĉi tio estas necesaj sed ne sufiĉaj kondiĉoj por ebeneco kaj ekstera ebeneco).
• Plena dukolora grafeo K_{{n, n}} estas grafeo de Moore kaj (n, 4)-kaĝo.
• Plena dukolora grafeo K_{{m, n}} havas vertican kovrantan nombron min {m, n} kaj lateran kovrantan nombron max {m, n}.
• Plena dukolora grafeo K_{{m, n}} havas maksimuman sendependan aron de amplekso max {m, n}.
• Plena dukolora grafeo K_{{m, n}} havas maksimuman kongruanton de amplekso min {m, n}.
• Plena dukolora grafeo K_{{n, n}} havas pozitivan n-lateran kolorigon.
• Plena dukolora grafeo K_{{m, n}} havas m^n-1 n^m-1 generantajn arbojn.
• La lastaj du rezultoj estas korolarioj de la geedziĝa teoremo se ĝi estas aplikita al k-regula dukolora grafeo.
• Plena dukolora grafeo K_{{n, n}} aŭ K_{{n, n+1}} estas grafeo de Turán.

Vidu ankaŭ

• Dukolora grafeo
• Kliko (grafeo)
• Nulgrafeo
• Plena grafeo
• Ciklo (grafeo)
• Vojo (grafeo)