Lovászovo číslo - Lovász number

v teorie grafů, Lovászovo číslo a graf je reálné číslo to je horní hranice na Shannonova kapacita grafu. Je také známý jako Funkce Lovász theta a je běžně označován ϑ (G). Toto množství poprvé představil László Lovász ve svém příspěvku z roku 1979 Na Shannonově kapacitě grafu.^[1]

Přesné numerické aproximace tohoto čísla lze vypočítat v polynomiální čas podle semidefinitní programování a elipsoidní metoda.Je vložen mezi chromatické číslo a číslo kliky libovolného grafu a lze je použít k výpočtu těchto čísel na grafech, pro které jsou stejná, včetně perfektní grafy.

Definice

Nechat G = (PROTI, E) být a graf na n vrcholy. Objednaná sada n jednotkové vektory U = (u_i | i ∈ PROTI) ⊂ R^N se nazývá ortonormální reprezentace z G v R^N, pokud u_i a u_j jsou kolmé, kdykoli vrcholy i a j nesousedí v G:

${ displaystyle u_ {i} ^ { mathrm {T}} u_ {j} = { začátek {případů} 1, & { text {if}} i = j, 0, & { text {pokud }} ij notin E. end {případy}}}$

Je zřejmé, že každý graf připouští ortonormální reprezentaci s N = n (pouze představují vrcholy odlišnými vektory z standardní základ z Rⁿ, ačkoli to obecně nebude věrné, pokud graf nebude bez okrajů; věrné zastoupení v N = n je také možné přidružením každého vrcholu k základnímu vektoru jako dříve, ale mapováním každého vrcholu na součet základních vektorů spojených s jeho sousedstvím), ale obecně by bylo možné vzít N podstatně menší než počet vrcholůn.

The Lovászovo číslo ϑ grafu G je definována takto:

${ displaystyle vartheta (G) = min _ {c, U} max _ {i ve V} { frac {1} {(c ^ { mathrm {T}} u_ {i}) ^ { 2}}},}$

kde C je jednotkový vektor v R^N a U je ortonormální reprezentace G v R^N. Zde se minimalizace implicitně provádí také přes dimenzi Nale bez ztráty obecnosti to stačí zvážit N = n.^[2] To intuitivně odpovídá minimalizaci polovičního úhlu rotace kužel obsahující všechny reprezentující vektory ortonormální reprezentace G. Pokud je optimální úhel ϕ, pak ϑ (G) = 1 / kos²(ϕ) a C odpovídá ose symetrie kužele.^[3]

Ekvivalentní výrazy

Nechat G = (PROTI, E) být grafem na n vrcholy. Nechat A rozsah přes všechny n × n symetrické matice takhle A_ij = 1 kdykoli i = j nebo ij ∉ Ea nechť λ_max(A) označují největší vlastní číslo z A. Pak alternativní způsob výpočtu Lovászova čísla G je následující:^[4]

${ displaystyle vartheta (G) = min _ {A} lambda _ { max} (A).}$

Následující metoda je duální oproti předchozí metodě. Nechat B rozsah přes všechny n × n symetrický pozitivní semidefinitní matice takhle b_ij = 0 pro každého ij ∈ E a Tr (B) = 1. Zde Tr označuje stopa (součet diagonálních záznamů) a J je n × n matice jedniček. Pak^[5]

${ displaystyle vartheta (G) = max _ {B} operatorname {Tr} (BJ).}$

Tr (BJ) je pouze součet všech záznamů z B.

Lovászovo číslo lze vypočítat také z hlediska doplňkový graf G. Nechat d být jednotkovým vektorem a PROTI = (proti_i | i ∈ PROTI) být ortonormální reprezentací G. Pak^[6]

${ displaystyle vartheta (G) = max _ {d, V} součet _ {i ve V} (d ^ { mathrm {T}} v_ {i}) ^ {2}.}$

Hodnota ϑ pro některé známé grafy

Graf	Hodnota ϑ[7]
Kompletní graf	${ displaystyle vartheta (K_ {n}) = 1}$
Prázdný graf	${ displaystyle vartheta ({ bar {K}} _ {n}) = n}$
Pentagon graf	${ displaystyle vartheta (C_ {5}) = { sqrt {5}}}$
Cyklické grafy	${ displaystyle vartheta (C_ {n}) = { begin {cases} { frac {n cos ( pi / n)} {1+ cos ( pi / n)}} & { text { pro liché}} n, { frac {n} {2}} a { text {pro sudé}} n end {případy}}}$
Petersenův graf	${ displaystyle vartheta (KG_ {5,2}) = 4}$
Kneserovy grafy	${ displaystyle vartheta (KG_ {n, k}) = { binom {n-1} {k-1}}}$
Kompletní multipartitní grafy	${ displaystyle vartheta (K_ {n_ {1}, tečky, n_ {k}}) = max _ {1 leq i leq k} n_ {i}}$

Vlastnosti

Li G ⊠ H označuje silný grafový produkt grafů G a H, pak^[8]

${ displaystyle vartheta (G boxtimes H) = vartheta (G) vartheta (H).}$

Li G je doplněk z G, pak^[9]

${ displaystyle vartheta (G) vartheta ({ bar {G}}) geq n,}$

s rovností, pokud G je vrchol-tranzitivní.

Lovász „sendvičová věta“

Lovászova „sendvičová věta“ uvádí, že Lovászovo číslo vždy leží mezi dvěma dalšími čísly, která jsou NP-kompletní počítat.^[10] Přesněji,

${ displaystyle omega (G) leq vartheta ({ bar {G}}) leq chi (G),}$

kde ω(G) je číslo kliky z G (velikost největší klika ) a χ(G) je chromatické číslo z G (nejmenší počet barev potřebných k vybarvení vrcholů G takže žádné dva sousední vrcholy neobdrží stejnou barvu).

Hodnota ${ displaystyle vartheta (G)}$ lze formulovat jako a semidefinitní program a číselně aproximován elipsoidní metoda v čase ohraničeném a polynomiální v počtu vrcholů G.^[11]Pro perfektní grafy, chromatické číslo a číslo kliky jsou stejné, a proto jsou stejné ${ displaystyle vartheta ({ bar {G}})}$. Výpočtem aproximace ${ displaystyle vartheta ({ bar {G}})}$ a poté zaokrouhlení na nejbližší celočíselnou hodnotu lze chromatické číslo a počet klik těchto grafů vypočítat v polynomiálním čase.

Vztah ke kapacitě Shannona

The Shannonova kapacita grafu G je definována takto:

${ displaystyle Theta (G) = sup _ {k} { sqrt [{k}] { alpha (G ^ {k})}} = lim _ {k rightarrow infty} { sqrt [ {k}] { alpha (G ^ {k})}},}$

kde α (G) je číslo nezávislosti z graf G (velikost největší nezávislá sada z G) a G^k je silný grafový produkt z G sám se sebou k krát. Jasně, Θ(G) ≥ α(G). Číslo Lovász však poskytuje horní hranici Shannonovy kapacity grafu,^[12] proto

${ displaystyle alpha (G) leq Theta (G) leq vartheta (G).}$

Pentagon graf

Nechť je například graf zaměnitelnosti kanálu C₅, a Pentagon. Vzhledem k tomu, původní papír Shannon (1956) bylo otevřeným problémem určit hodnotu Θ (C₅). Poprvé byla založena Lovász (1979) to Θ (C₅) = √5.

Je zřejmé, že Θ (C₅) ≥ α (C₅) = 2. Avšak α (C₅²) ≥ 5, protože „11“, „23“, „35“, „54“, „42“ je pět vzájemně nezaměnitelných zpráv (tvořící nezávislou množinu pěti vrcholů v silném čtverci C₅), tedy Θ (C₅) ≥ √5.

Abychom ukázali, že tato vazba je těsná, dovolte U = (u₁, ..., u₅) být následující ortonormální reprezentace pětiúhelníku:

${ displaystyle u_ {k} = { začátek {pmatrix} cos { theta} sin { theta} cos { varphi _ {k}} sin { theta} sin { varphi _ {k}} end {pmatrix}}, quad cos { theta} = { frac {1} { sqrt [{4}] {5}}}, quad varphi _ {k} = { frac {2 pi k} {5}}}$

a nechte C = (1, 0, 0). Použitím této volby v počáteční definici Lovászova čísla získáme ϑ(C₅) ≤ √5. Proto,, (C₅) = √5.

Existují však grafy, u nichž se Lovászovo číslo a Shannonova kapacita liší, takže Lovászovo číslo nelze obecně použít k výpočtu přesné Shannonovy kapacity.^[13]

Kvantová fyzika

Lovászovo číslo bylo zobecněno pro „nekomutativní grafy“ v kontextu kvantová komunikace^[14]. Rovněž vzniká číslo Lovasz kvantová kontextualita^[15] ve snaze vysvětlit sílu kvantové počítače.^[16]

Viz také

• Funkce Tardos, monotónní aproximace Lovászova čísla doplňkový graf který lze vypočítat v polynomiálním čase a byl použit k prokázání dolních mezí v složitost obvodu

Poznámky

Reference

externí odkazy

• Weisstein, Eric W. "Lovászovo číslo". MathWorld.
• Weisstein, Eric W. „Sandwichova věta“. MathWorld.
• Weisstein, Eric W. "Shannonova kapacita". MathWorld.