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, S ⊂ V 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.

- A feszített utak olyan feszített részgráfok, melyek utak. Egy súlyozatlan gráf két csúcsa közötti legrövidebb út mindig feszített út, hiszen a feszítettséget megszüntető bármely további él miatt már nem lenne a legrövidebb sem. Megfordítva, a távolság-örökletes gráfok minden feszített útja legrövidebb út.[2]
- A feszített körök olyan feszített részgráfok, melyek körök. Egy gráf girthparaméterét legrövidebb körének hossza határozza meg – ez a kör mindig feszített kör. Az erős perfektgráf-tétel szerint a feszített körök és komplementereik kritikus szerepet játszanak a perfekt gráfok jellemzésében.[3]
- A klikkek és független csúcshalmazok olyan feszített részgráfok, melyek teljes gráfok vagy üres gráfok.
- Egy csúcs szomszédsága a vele szomszédos összes csúcs feszített részgráfjával egyezik meg.
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
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads