Plena dukolora grafeo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
La artikolo estas parto de serio pri grafeteorio.




Plej gravaj terminoj
grafeo
arbo
subgrafeo
ciklo
kliko
grado de vertico
grado de grafeo


Elektitaj klasoj de grafejo
plena grafeo
plena dukolora grafeo
kohera grafeo
arbo
grafeo dudivdebla
Fenda grafeo
regula grafeo
grafeo de Euler
grafeo de Hamilton
grafeo senrelifa


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


Alijaj
kodo de Gray
diagramo de Hasse
kodo de Prüfer


Reprezentado de grafeo Glosaro de grafeteorio


vidi  diskuti  redakti
Plena dukolora grafeo
Plia nomo Dukliko
Bildo
Plena dukolora grafeo kun m=3, n=2
Verticoj m+n
Lateroj mn
Aŭtomorfioj 2m!n! se m=n,
m!n! se m≠n
v  d  r
Information icon.svg

En grafeteorio, plena dukolora grafeodukliko estas speciala speco 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 = (V1 + V2, E) estas dukolora grafeo tia ke por ĉiuj du verticoj v_1 \in V_1 kaj v_2 \in V_2, estas latero v1v2 en G.

Pro tio ke la grafeo estas dukolora, por ĉiuj du verticoj v_1 \in V_1 kaj v_2 \in V_1, latero v1v2 ne estas en G; ankaŭ por ĉiuj du verticoj v_1 \in V_2 kaj v_2 \in V_2, latero v1v2 ne estas en G.

Plena dukolora grafeo kun dispartigoj de ampleksoj |V1|=m kaj |V2|=n estas skribata kiel K{m, n}.

Por ĉiu k, K{1, k} estas nomata kiel stelo. La grafeo K{1, 3} estas nomata kiel ungego.

Ekzemploj[redakti | redakti fonton]

Complete bipartite graph K3,1.svg
K1,3
Complete bipartite graph K3,2.svg
K2,3
Complete bipartite graph K3,3.svg
K3,3

Propraĵoj[redakti | redakti fonton]

Vidu ankaŭ[redakti | redakti fonton]