Whitney-síksági kritérium

A Whitney-síksági kritérium síkgráfok matroid leírása . A kritérium Hassler Whitney [1] nevéhez fűződik . A kritérium kimondja, hogy egy G gráf akkor és csak akkor sík, ha grafikus matroidja egyben kográf is (vagyis egy másik grafikus matroid kettős matroidja

A tiszta gráfelmélet szempontjából ez a kritérium a következőképpen fogalmazható meg: léteznie kell egy másik (kettős) gráfnak G '=( V ', E '), és bijektív megfeleltetésnek kell lennie az eredeti G gráf E ' élei és E élei között . hogy az E élek T részhalmaza akkor és csak akkor képezi a G gráf feszítőfáját, ha az E - T halmaz komplementerének megfelelő élek a G ' gráf feszítőfáját alkotják .

A síkosságnak más kritériumai is vannak , például a Pontrjagin-Kuratovszkij-tétel .

Algebrai kettősség

A Whitney-kritérium egy ekvivalens formája azt mondja, hogy egy G gráf akkor és csak akkor sík, ha van egy duális gráfja, amelynek grafikus matroidja duális G grafikus matroidjával . Az olyan gráfot, amelynek grafikus matroidja duális G grafikus matroidjával, G algebrai duálisaként ismert . Ekkor a Whitney-féle síkossági kritérium a következőképpen fogalmazható meg: egy gráf akkor és csak akkor sík, ha algebrailag duális gráfja van.

Topológiai kettősség

Ha egy gráf egy topológiai felületbe, például egy síkba van beágyazva úgy, hogy bármely beágyazófelület topológiai lemez, akkor a kettős beágyazású gráf egy H gráfként (bizonyos esetekben multigráfként ) van definiálva, amelynek mindegyikhez van egy csúcsa. beágyazási felület és egy él minden szomszédos oldalpárhoz. A Whitney-kritérium szerint a következő feltételek egyenértékűek:

Lehetőség van nem sík felületekbe, például tóruszba ágyazott gráfok kettős gráfjainak meghatározására, de az ilyen kettős gráfok általában nem felelnek meg a Whitney-kritérium által megkövetelt vágásoknak, ciklusoknak és feszítőfáknak.

Jegyzetek

  1. Whitney, 1932 , p. 339–362.
  2. Tutte, 1965 , p. 1–47.

Irodalom