Feszített részgráf – Wikipédia

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 \subset 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.

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.

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

↑ Diestel, Reinhard (2006), Graph Theory, vol. 173, Graduate texts in mathematics, Springer-Verlag, pp. 3–4, ISBN 9783540261834, <https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA3>.
↑ Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics. Oxford. Second Series 28 (112): 417–420, doi:10.1093/qmath/28.4.417, <http://qjmath.oxfordjournals.org/cgi/reprint/28/4/417>.
↑ Chudnovsky, Maria; Robertson, Neil & Seymour, Paul et al. (2006), "The strong perfect graph theorem", Annals of Mathematics 164 (1): 51–229, doi:10.4007/annals.2006.164.51, <http://annals.princeton.edu/annals/2006/164-1/p02.xhtml>.
↑ Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms 6 (3): 434–451, DOI 10.1016/0196-6774(85)90012-4.

Matematikaportál • összefoglaló, színes tartalomajánló lap

[1] Diestel, Reinhard (2006), Graph Theory, vol. 173, Graduate texts in mathematics, Springer-Verlag, pp. 3–4, ISBN 9783540261834, <https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA3>.

[2] Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics. Oxford. Second Series 28 (112): 417–420, doi:10.1093/qmath/28.4.417, <http://qjmath.oxfordjournals.org/cgi/reprint/28/4/417>.

[3] Chudnovsky, Maria; Robertson, Neil & Seymour, Paul et al. (2006), "The strong perfect graph theorem", Annals of Mathematics 164 (1): 51–229, doi:10.4007/annals.2006.164.51, <http://annals.princeton.edu/annals/2006/164-1/p02.xhtml>.

[4] Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms 6 (3): 434–451, DOI 10.1016/0196-6774(85)90012-4.

[1]

[2]

[3]

[4]