Indukovaný podgraf - Induced subgraph

v teorie grafů, an indukovaný podgraf grafu je další graf, vytvořený z a podmnožina vrcholů grafu a všech okrajů spojujících páry vrcholů v této podmnožině.

Definice

Formálně, pojďme G = (PROTI, E) být libovolný graf, a nechť S ⊂ PROTI být libovolnou podmnožinou vrcholů G. Pak indukovaný podgraf G[S] je graf, jehož množina vrcholů je S a jehož sada hran se skládá ze všech hran v E které mají oba koncové body v S.^[1] Stejná definice funguje neorientované grafy, řízené grafy, a dokonce multigrafy.

Indukovaný podgraf G[S] lze také nazvat subgraf indukovaný v G podle S, nebo (pokud si vybere kontext G jednoznačný) indukovaný podgrafS.

Příklady

Mezi důležité typy indukovaných podgrafů patří následující.

The had-in-the-box problém se týká nejdelší indukované cesty v hyperkrychlové grafy

• Vyvolané cesty jsou indukované podgrafy, které jsou cesty. The nejkratší cesta mezi libovolnými dvěma vrcholy v neváženém grafu je vždy indukovaná cesta, protože jakékoli další hrany mezi dvojicemi vrcholů, které by mohly způsobit její neindukci, by také způsobily, že nebude nejkratší. Naopak v vzdálenostně dědičné grafy, každá indukovaná cesta je nejkratší cestou.^[2]
• Indukované cykly jsou indukované podgrafy nebo cykly. The obvod grafu je definována délkou jeho nejkratšího cyklu, který je vždy indukovaným cyklem. Podle silná dokonalá věta o grafu, indukované cykly a jejich doplňuje hrají zásadní roli při charakterizaci perfektní grafy.^[3]
• Kliky a nezávislé sady jsou indukované podgrafy, které jsou kompletní grafy nebo bez okrajů grafy.
• Vyvolané shody jsou indukované podgrafy, které jsou párování.
• The sousedství vrcholu je indukovaný podgraf všech vrcholů sousedících s ním.

Výpočet

The problém isomorfismu indukovaného podgrafu je forma problém izomorfismu podgrafu ve kterém cílem je otestovat, zda lze jeden graf najít jako indukovaný podgraf jiného. Protože zahrnuje klika problém jako zvláštní případ to je NP-kompletní.^[4]

Reference