Podgraf
V teorii grafů je podgrafem graf obsažený v jiném grafu. Formálně je graf podgrafem if a . Množina vrcholů podgrafu je podmnožinou množiny vrcholů a množina oblouků je podmnožinou množiny oblouků, které mají svůj původ a jejich konec mezi vrcholy .
H=(PROTIH,EH){\ displaystyle H = (V_ {H}, E_ {H})}G=(PROTIG,EG){\ displaystyle G = (V_ {G}, E_ {G})}PROTIH⊆PROTIG{\ displaystyle V_ {H} \ subseteq V_ {G}}EH⊆{(X,y)∈EG∣X∈PROTIH∧y∈PROTIH}{\ displaystyle E_ {H} \ subseteq \ {(x, y) \ v E_ {G} \ střední x \ ve V_ {H} \ klín y \ ve V_ {H} \}}H{\ displaystyle H}G{\ displaystyle G}H{\ displaystyle H}G{\ displaystyle G}H{\ displaystyle H}
Překlenující subgraph nebo částečné graf je subgraph mající stejnou množinu vrcholů, jako je graf, který jej obsahuje. Formálně jde o sub-graf pokrývající ( tj. Obal ), pokud a . Jakýkoli jednoduchý graf s n vrcholy je tedy podgrafem pokrývajícím celý graf K n .
H{\ displaystyle H}G{\ displaystyle G} H{\ displaystyle H} G{\ displaystyle G}PROTIH=PROTIG{\ displaystyle V_ {H} = V_ {G}}EH⊆EG{\ displaystyle E_ {H} \ subseteq E_ {G}}
Indukované subgraph je subgraph omezením grafu na podmnožinu vrcholů. Formálně je indukovaný podgraf , jestliže pro každou dvojici vrcholů , je spojen s v případě, a pouze tehdy, když je spojen s v . Další formulace podmínky: množina oblouků je množina dopadajících oblouků se dvěma vrcholy .
H{\ displaystyle H}G{\ displaystyle G}(X,y){\ displaystyle (x, y)}H{\ displaystyle H}X{\ displaystyle x}y{\ displaystyle}H{\ displaystyle H}X{\ displaystyle x}y{\ displaystyle}G{\ displaystyle G}H{\ displaystyle H}G{\ displaystyle G}H{\ displaystyle H}
Podívejte se také
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">