Plena dukolora grafeo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
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 kaj , estas eĝo v1v2 en E.

Pro tio ke la grafeo estas dukolora, por ĉiuj du verticoj kaj , eĝo v1v2 ne estu en G; same por kaj .

Plena dukolora grafeo kies dispartigoj havas vertic-nombrojn |V1|=m kaj |V2|=n estas skribata kiel K{m, n}.

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

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
La stelgrafeoj K1,3, K1,4, K1,5, kaj K1,6.


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 grafeoj
plena grafeo
plena dukolora grafeo
kohera grafeo
arbo
grafeo dudividebla
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


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


Reprezentado de grafeo Glosaro de grafeteorio


vidi  diskuti  redakti

Propraĵoj[redakti | redakti fonton]

Vidu ankaŭ[redakti | redakti fonton]