Sűrű gráf

A matematika, azon belül a gráfelmélet területén egy sűrű gráf alatt olyan gráfot értünk, melyben az élek száma közel áll az élek maximális lehetséges számához. Ennek az ellentéte, a ritka gráf a viszonylag kevés éllel rendelkező gráf. A sűrű és ritka gráfok közötti különbségtétel önkényes, a szövegkörnyezettől függhet.

Irányítatlan egyszerű gráfokon egy gráf sűrűsége a következővel egyezik meg:

Irányított egyszerű gráfok sűrűsége pedig így határozható meg:

ahol E a gráf éleinek, V a csúcsainak a száma. Irányítatlan gráfban az élek maximális száma ½ |V| (|V|−1), tehát a maximális sűrűség 1 (a teljes gráfok esetében), a minimális pedig 0 .

Felső sűrűség A felső sűrűség a gráfsűrűség fogalmának kiterjesztése véges gráfokról végtelen gráfokra. Intuitív megközelítésben egy végtelen gráfnak lehetnek a felső sűrűségénél kisebb sűrűségű, tetszőlegesen nagy véges részgráfjai, de nem lehetnek a felső sűrűségnél nagyobb sűrűségű, tetszőlegesen nagy véges részgráfjai. Formálisan, egy G gráf felső sűrűsége azon α értékek infimuma, melyekre G α sűrűségű véges részgráfjai korlátos számú csúccsal rendelkezhetnek. Az Erdős–Stone-tétel segítségével megmutatható, hogy a felső sűrűség értéke vagy 1, vagy a szuperpartikuláris arányok valamelyike: 0, 1/2, 2/3, 3/4, 4/5, ... n/(n + 1), ... (lásd pl. Diestel, p. 189).

Ritka és éles gráfok és definíciója szerint egy (k,l)-ritka gráf (sparse graph) minden nem üres részgráfjának n csúcsa között legfeljebb kn − l él húzódik, a (k,l)-éles gráf (tight graph)az „éles” szó itt a matematikai zsargonban használt éles, tovább már nem javítható eredményre utal pedig (k,l)-ritka és pontosan kn − l éllel rendelkezik. Így a fák az (1,1)-éles gráfokkal egyeznek meg, az erdők az (1,1)-ritka gráfok, a k arboricitású gráfok pedig a (k,k)-ritka gráfok. A pszeudoerdők (az összefüggő komponensenként legfeljebb 1 körrel rendelkező irányítatlan gráfok) az (1,0)-ritka gráfokkal egyeznek meg, a merevségelmélet Laman-gráfjai pedig a (2,3)-éles gráfokkal.

Más, a ritkaságukkal nem jellemezhető gráfcsaládokról is tehetők hasonló kijelentések. Például az n csúcsú síkgráfok legfeljebb 3n − 6 éllel rendelkeznek, és bármely síkgráf részgráfjai is síkgráf – ebből a két kijelentésből következik, hogy a síkgráfok (3,6)-ritka gráfok. Nem igaz viszont, hogy bármely (3,6)-ritka gráf síkgráf lenne. Hasonlóan kijelenthető, hogy a külsíkgráfok (2,3)-ritkák és a páros síkgráfok (2,4)-ritkák.

Streinu és Theran igazolta, hogy a (k,l)-ritkaságra való tesztelés polinom időben elvégezhető, ha k és l olyan egész számok, melyekre 0 ≤ l < 2k.

Ha egy gráfcsalád esetén létezik olyan k és l, melyekre a családbéli gráfok (k,l)-ritkák, akkor a gráfok degeneráltsága vagy arboricitása korlátos. Precízebben kimondva, eredményéből következik, hogy a legfeljebb a arboricitású gráfok éppen az (a,a)-ritka gráfok; a legfeljebb d degeneráltságú gráfok pedig éppen a ((d + 1)/2,1)-ritka gráfok.

Ritka és sűrű gráfosztályok arra jutott, hogy a ritkaság/sűrűség dichotómia miatt szükséges egyes gráfok helyett végtelen gráfosztályokat tekintetbe venni. Úgy definiálták a valahol sűrű (somewhere dense) gráfosztályt, mint azokat a gráfosztályokat, melyekben létezik t küszöbérték, melyre minden teljes gráf megjelenik az osztály egy gráfjának t-felosztásaként. Ha ilyen küszöbérték nem létezik, a gráfosztály sehol sem sűrű (nowhere dense). A sehol sem sűrű és valahol sűrű gráfosztályok dichotómiáját elemzik.

A korlátos degeneráltságú gráfok és a sehol sem sűrű gráfok mind beletartoznak a biklikkmentes gráfok osztályába, melyek a teljes páros gráfot részgráfként nem tartalmazó gráfcsaládok.

Kapcsolódó szócikkek

Sűrű részgráf

Fordítás

Jegyzetek

Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005. . . .

.

. . .

Kategória:Gráfcsaládok