Feszített részgráf

gráfelméleti fogalom From Wikipedia, the free encyclopedia

Remove ads

A matematika, azon belül a gráfelmélet területén egy gráf feszített részgráfja (induced subgraph) egy olyan gráf, melynek csúcsai az eredeti gráf csúcsainak egy részhalmaza, élei pedig a részhalmazban szereplő csúcsokat összekötő élek. Másként fogalmazva, H feszített részgráfja G-nek, ha úgy adódik, hogy vesszük G bizonyos csúcsait és minden köztük futó élt.

Definíció

Formálisan, legyen G = (V, E) tetszőleges gráf, SV pedig G csúcsainak egy részhalmaza. Ekkor a G[S] feszített részgráf az a gráf, melynek csúcshalmaza S, élhalmazát pedig az E-ben lévő összes olyan él alkotja, melynek mindkét végpontja S-ben található.[1] Ugyanez a definíció működik irányítatlan és irányított gráfokra, sőt akár multigráfokra is.

A G[S] feszített részgráf helyett azt is lehet mondani, hogy az S G-ben kifeszített részgráfja, vagy akár (ha a kontextusból egyértelmű, hogy a G-ről van szó) az S feszített részgráfja.

Remove ads

Példák

Az alábbiakban olvasható néhány fontosabb példa a feszített részgráfokra.

Thumb
A snake-in-the-box („kígyó a dobozban”) probléma a hiperkockagráfok leghosszabb feszített útjaival foglalkozik
Remove ads

Számítási bonyolultság

A feszített részgráf izomorfizmus-probléma a részgráfizomorfizmus-probléma alesete, melyben a cél annak vizsgálata, hogy egy gráf előállítható-e egy másik gráf feszített részgráfjaként. Mivel a klikkproblémát speciális esetként tartalmazza, NP-teljes.[4]

Jegyzetek

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads