| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a síkgráf-elválasztási tétel, síkgráf-felbontási tétel, síkgráf-szeparációs tétel vagy Lipton–Tarjan-szeparátortétel (planar separator theorem) a síkbarajzolható gráfokra vonatkozó egyfajta izoperimetrikus egyenlőtlenség, ami kimondja, hogy bármely síkbarajzolható gráf kis számú csúcs eltávolításával kisebb darabokra szedhető szét. Pontosabban, egy n csúcsú gráfból O(√n) csúcsot eltávolítva (ahol O a nagy Ordó jelölésre utal) a gráfot olyan diszjunkt részgráfokra , melyek mindegyikében legfeljebb 2n/3 csúcs található. A szeparációs tételnek először egy gyengébb változatát sikerült bizonyítania -nak, melyben a szeparátor O(√n) helyett O(√n log n) csúcsból áll; az éles aszimptotikus korlátot elsőként igazolta. Azóta a szeparátortételt sokféleképpen sikerült bizonyítani, a tételben szereplő O(√n) tagot javították és a tételt kiterjesztették a nem síkbarajzolható gráfok egyes osztályaira is. A síkgráf-elválasztási tétel ismételt alkalmazása egy szeparátorhierarchiát hoz létre, ami a gráf vagy (branch-decomposition) formáját öltheti. Ezek a szeparátorhierarchiák felhasználhatók síkgráfokon futtatott hatékony „oszd meg és uralkodj”-algoritmusok létrehozására, és az ezeken a hierarchiákon végzett segítségével ezen gráfok általában optimalizációs problémáit megoldó vagy algoritmusok előállítására. A szeparátorhierarchiákat használják a (kb. „egymásba ágyazott boncolás”) módszerében is, ami a végeselemes módszerben fellépő ritka lineáris egyenletrendszerek megoldásának hatékony, Gauss-eliminációs variánsa. , Fomin, és Thilikos -elmélete a síkgráf-elválasztási tételt általánosítja és nagyban kiterjeszti az alkalmazási területét a síkbarajzolható gráfok rengeteg minimalizálási problémája mellett az egy-egy tiltott minort nem tartalmazó gráfokra. (hu)
- A matematika, azon belül a gráfelmélet területén a síkgráf-elválasztási tétel, síkgráf-felbontási tétel, síkgráf-szeparációs tétel vagy Lipton–Tarjan-szeparátortétel (planar separator theorem) a síkbarajzolható gráfokra vonatkozó egyfajta izoperimetrikus egyenlőtlenség, ami kimondja, hogy bármely síkbarajzolható gráf kis számú csúcs eltávolításával kisebb darabokra szedhető szét. Pontosabban, egy n csúcsú gráfból O(√n) csúcsot eltávolítva (ahol O a nagy Ordó jelölésre utal) a gráfot olyan diszjunkt részgráfokra , melyek mindegyikében legfeljebb 2n/3 csúcs található. A szeparációs tételnek először egy gyengébb változatát sikerült bizonyítania -nak, melyben a szeparátor O(√n) helyett O(√n log n) csúcsból áll; az éles aszimptotikus korlátot elsőként igazolta. Azóta a szeparátortételt sokféleképpen sikerült bizonyítani, a tételben szereplő O(√n) tagot javították és a tételt kiterjesztették a nem síkbarajzolható gráfok egyes osztályaira is. A síkgráf-elválasztási tétel ismételt alkalmazása egy szeparátorhierarchiát hoz létre, ami a gráf vagy (branch-decomposition) formáját öltheti. Ezek a szeparátorhierarchiák felhasználhatók síkgráfokon futtatott hatékony „oszd meg és uralkodj”-algoritmusok létrehozására, és az ezeken a hierarchiákon végzett segítségével ezen gráfok általában optimalizációs problémáit megoldó vagy algoritmusok előállítására. A szeparátorhierarchiákat használják a (kb. „egymásba ágyazott boncolás”) módszerében is, ami a végeselemes módszerben fellépő ritka lineáris egyenletrendszerek megoldásának hatékony, Gauss-eliminációs variánsa. , Fomin, és Thilikos -elmélete a síkgráf-elválasztási tételt általánosítja és nagyban kiterjeszti az alkalmazási területét a síkbarajzolható gráfok rengeteg minimalizálási problémája mellett az egy-egy tiltott minort nem tartalmazó gráfokra. (hu)
|
