Sottografo indotto - Induced subgraph

Nella teoria dei grafi , un sottografo indotto di un grafo è un altro grafo, formato da un sottoinsieme dei vertici del grafico e tutti i bordi (dal grafico originale) che collegano coppie di vertici in quel sottoinsieme.

Definizione

Formalmente, sia un grafo qualsiasi e sia un sottoinsieme di vertici di G . Quindi il sottografo indotto è il grafo il cui insieme di vertici è e il cui insieme di archi è costituito da tutti gli archi in che hanno entrambi gli estremi in . Cioè, per qualsiasi due vertici , e sono adiacenti in se e solo se sono adiacenti in . La stessa definizione funziona per grafi non orientati , grafi orientati , e persino multigrafi . ${\displaystyle G=(V,E)}$${\displaystyle S\subset V}$${\displaystyle G[S]}$${\displaystyle S}$${\displaystyle E}$${\displaystyle S}$${\displaystyle u,v\in S}$${\displaystyle u}$${\displaystyle v}$${\displaystyle G[S]}$${\displaystyle G}$

Il sottografo indotto può anche essere chiamato sottografo indotto da , o (se il contesto rende la scelta non ambigua) sottografo indotto di . ${\displaystyle G[S]}$${\displaystyle G}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$

Esempi

I tipi importanti di sottografi indotti includono quanto segue.

Il problema snake-in-the-box riguarda i percorsi indotti più lunghi nei grafi ipercubo

• I percorsi indotti sono sottografi indotti che sono percorsi . Il percorso più breve tra due vertici qualsiasi in un grafo non pesato è sempre un percorso indotto, perché qualsiasi arco aggiuntivo tra coppie di vertici che potrebbe impedirne l'induzione lo farebbe anche non essere il più corto. Viceversa, nei grafici ereditari a distanza , ogni cammino indotto è un cammino minimo.
• I cicli indotti sono sottografi indotti che sono cicli . La circonferenza di un grafico è definita dalla lunghezza del suo ciclo più breve, che è sempre un ciclo indotto. Secondo il teorema del grafo perfetto forte , i cicli indotti ei loro complementi giocano un ruolo fondamentale nella caratterizzazione dei grafi perfetti .
• Le cricche e gli insiemi indipendenti sono sottografi indotti che sono rispettivamente grafici completi o grafici senza bordi .
• Gli abbinamenti indotti sono sottografi indotti che sono corrispondenze .
• L' intorno di un vertice è il sottografo indotto di tutti i vertici ad esso adiacenti.

Calcolo

Il problema dell'isomorfismo del sottografo indotto è una forma del problema dell'isomorfismo del sottografo in cui l'obiettivo è verificare se un grafo può essere trovato come sottografo indotto di un altro. Poiché include il problema della cricca come caso speciale, è NP-completo .

Riferimenti