Oberoende set

En oberoende uppsättning i grafteori kan antingen vara en oberoende uppsättning av hörn eller en oberoende uppsättning kanter. Oberoende uppsättningar beaktas i grafer som täcker problem.

En oberoende uppsättning av hörn

I en oriktad graf kallas uppsättningen av dess hörn , där , oberoende (eller i sig stabil ), om några två hörn i den inte är intill varandra, det vill säga inget par hörn är sammankopplade med en kant [1] [2] [3] , eller med andra ord, uppsättningen genererar en tom subgraf: $G=(V,E)$ $S$ $S\delmängd V$ $S$

G(S,E^{\prime })\subset G~~\Rightarrow ~~E^{\prime }=\varnothing

Det största antalet hörn i sådana uppsättningar kallas för vertexoberoendetalet (ibland bara oberoendetalet ) i grafen [1] , det vill säga om det finns en familj av alla oberoende uppsättningar av hörn , då [4] . $\beta _{0}(G)$ $G$ $F$ $S$ ${\displaystyle \beta _{0}(G)=\max\{|S|:S\in Q\))$

En oberoende uppsättning kanter

I en oriktad graf kallas uppsättningen av dess kanter , där , oberoende om inget par kanter är intill [1] [3] eller om uppsättningen genererar en tom subgraf: $G=(V,E)$ $M$ $M\subset E$ $M$

G(V^{\prime },M)\subset G~~\Rightarrow ~~V^{\prime }=\varnothing

Det största antalet kanter i sådana uppsättningar kallas grafens oberoende kantnummer , det vill säga om det finns en familj av alla oberoende uppsättningar kanter , då . $\beta _{1}(G)$ $G$ $W$ $M$ ${\displaystyle \beta _{1}(G)=\max\{|M|:M\in W\))$

Uppsättningen av oberoende kanter kallas också en matchning [5] . Därför kallas en oberoende uppsättning som har ett kardinalnummer den största matchningen av grafen . $M$ $\beta _{1}$ $G$

Anteckningar

↑ 1 2 3 Chartran, 2009 , sid. 98.
↑ Christofides, 1978 , sid. 44.
↑ 1 2 Harari, 1973 , sid. 118.
↑ Christofides, 1978 , sid. 45.
↑ Harari, 1973 , sid. 119.

Litteratur

Chartran G., Zhang P. Chromatic Graph Theory (engelska) / Serieredaktör Kenneth H. Rosen. - Baca Ration, London, New York: Chapman & Hall/CRC, 2009. - S. 483. - (Diskret matematik och dess tillämpningar). - ISBN 978-1-58488-800-0 .
Christofides N. Grafteori. Algoritmiskt tillvägagångssätt. . - M . : Mir, 1978. - 432 sid. (ryska)
Harari F. Grafteori. . — M .: Mir, 1973. — 300 sid. (ryska)