Johnsonův graf - Johnson graph - Wikipedia

Johnsonův graf
Johnsonův graf J(5,2)
Pojmenoval podle	Selmer M. Johnson
Vrcholy	${ displaystyle { binom {n} {k}}}$
Hrany	${ displaystyle { frac {1} {2}} k (n-k) { binom {n} {k}}}$
Průměr	${ displaystyle min (k, n-k)}$
Vlastnosti	${ displaystyle k (n-k)}$-pravidelný Vrchol-tranzitivní Přechodná vzdálenost Hamilton připojen
Zápis	${ displaystyle J (n, k)}$
Tabulka grafů a parametrů

Johnsonovy grafy jsou speciální třídou neorientované grafy definováno ze systémů množin. Vrcholy Johnsonova grafu ${ displaystyle J (n, k)}$ jsou ${ displaystyle k}$-prvkové podmnožiny souboru ${ displaystyle n}$- sada prvků; dva vrcholy sousedí, když průsečík dvou vrcholů (podmnožin) obsahuje ${ displaystyle (k-1)}$-elementy.^[1] Oba Johnson grafy a úzce související Johnsonovo schéma jsou pojmenovány po Selmer M. Johnson.

Speciální případy

• ${ displaystyle J (n, 1)}$ je kompletní graf K._n.
• ${ displaystyle J (4,2)}$ je oktaedrický graf.
• ${ displaystyle J (5,2)}$ je doplňkový graf z Petersenův graf,^[1] proto hranový graf z K.₅. Obecněji pro všechny ${ displaystyle n}$, Johnsonův graf ${ displaystyle J (n, 2)}$ je doplňkem Kneserův graf ${ displaystyle K (n, 2).}$

Graficko-teoretické vlastnosti

• ${ displaystyle J (n, k)}$ je izomorfní s ${ displaystyle J (n, n-k).}$

• Pro všechny ${ displaystyle 0 leq j leq operatorname {diam} (J (n, k))}$, libovolný pár vrcholů ve vzdálenosti ${ displaystyle j}$ podíl ${ displaystyle k-j}$ společné prvky.

• ${ displaystyle J (n, k)}$ je Hamilton připojen, což znamená, že každá dvojice vrcholů tvoří koncové body a Hamiltonova cesta v grafu. To zejména znamená, že má hamiltonovský cyklus.^[2]

• Je také známo, že Johnsonův graf ${ displaystyle J (n, k) ~}$ je${ displaystyle ~ k (n-k)}$-vertex-connected.^[3]

• ${ displaystyle J (n, k)}$ tvoří graf vrcholů a okrajů (n - 1) -dimenzionální polytop, nazvaný a hypersimplex.^[4]

• the číslo kliky z ${ displaystyle J (n, k)}$ je dán výrazem ve smyslu jeho nejmenších a největších vlastních čísel: ${ displaystyle omega (J (n, k)) = 1 - { tfrac { lambda _ { max}} { lambda _ { min}}}.}$

• The chromatické číslo z ${ displaystyle J (n, k)}$ je nanejvýš ${ Displaystyle n, chi (J (n, k)) leq n.}$^[5]

Automorfická skupina

Tady je vzdálenost-tranzitivní podskupina ${ displaystyle operatorname {Aut} (J (n, k))}$ izomorfní s ${ displaystyle operatorname {Sym} (n)}$. Ve skutečnosti, ${ displaystyle operatorname {Aut} (J (n, k)) cong operatorname {Sym} (n)}$, pokud ${ displaystyle n = 2k geq 4}$; v opačném případě, ${ displaystyle operatorname {Aut} (J (n, k)) cong operatorname {Sym} (n) krát C_ {2}}$.^[6]

Křižovatkové pole

V důsledku toho, že jsme přechodní na vzdálenost, ${ displaystyle J (n, k)}$ je také vzdálenost-pravidelná. Pronájem ${ displaystyle d}$ označit jeho průměr, průnik pole ${ displaystyle J (n, k)}$ darováno

${ displaystyle left {b_ {0}, ldots, b_ {d-1}, c_ {1}, ldots c_ {d} right }}$

kde:

${ displaystyle { begin {zarovnáno} b_ {j} & = (kj) (nkj) && 0 leq j$

Ukázalo se, že pokud ${ displaystyle J (n, k)}$ je ${ displaystyle J (8,2)}$, jeho průsečíkové pole není sdíleno s žádným jiným odlišným pravidelným grafem vzdálenosti; pole křižovatky ${ displaystyle J (8,2)}$ je sdílen se třemi dalšími pravidelnými grafy vzdálenosti, které nejsou Johnsonovými grafy.^[1]

Vlastní čísla a vlastní vektory

• Charakteristický polynom z ${ displaystyle J (n, k)}$ darováno

${ displaystyle phi (x): = prod _ {j = 0} ^ { operatorname {diam} (J (n, k))} left (x-A_ {n, k} (j) right ) ^ {{ binom {n} {j}} - { binom {n} {j-1}}}.}$

kde ${ displaystyle A_ {n, k} (j) = (k-j) (n-k-j) -j.}$^[6]

• Vlastní vektory ${ displaystyle J (n, k)}$ mít explicitní popis.^[7]

Johnsonovo schéma

Johnsonův graf ${ displaystyle J (n, k)}$ úzce souvisí s Johnsonovo schéma, an asociační schéma ve kterém každý pár k-element sets is associated with a number, half size of the symetrický rozdíl ze dvou sad.^[8] Johnsonův graf má výhodu pro každou dvojici sad ve vzdálenosti jedna v asociačním schématu a vzdálenosti v asociačním schématu jsou přesně nejkratší cesta vzdálenosti v Johnsonově grafu.^[9]

Johnsonovo schéma souvisí také s další rodinou dálkově přechodných grafů, s liché grafy, jehož vrcholy jsou ${ displaystyle k}$-prvkové podmnožiny souboru ${ displaystyle (2k + 1)}$-prvková sada a jejíž okraje odpovídají nesouvislým párům podmnožin.^[8]

Otevřené problémy

Vlastnosti expanze vrcholů Johnsonových grafů, stejně jako struktura odpovídajících extrémních sad vrcholů dané velikosti, nejsou plně pochopeny. Nedávno však byla získána asymptoticky těsná dolní mez expanze velkých sad vrcholů.^[10]

Obecně je stanovení chromatického čísla Johnsonova grafu otevřeným problémem.^[11]

Viz také

• Grassmannův graf

Reference

externí odkazy

• Weisstein, Eric W. „Johnsonův graf“. MathWorld.
• Brouwer, Andries E. „Johnsonovy grafy“.