Dato un semplice grafo diretto G = (V, E) un ciclo indotto è un ciclo in cui non ci sono due vertici del ciclo con un margine che non è nel ciclo.
(I cicli senza corde sono cicli indotti con a lease 4 vertici).
La mia domanda è qual è il numero massimo di cicli indotti che può avere un semplice grafico diretto?
Ho guardato un po 'intorno al web. Tuttavia non sono stato in grado di trovare una risposta a questa domanda specifica.
Se il grafico è diretto, ciò implica che nessun ciclo può contenere lo stesso bordo due volte.
Se il grafico è semplice (supponendo che tu intenda davvero un grafico semplice ), ciò implica che non ci sono "loop" "i bordi iniziano e finiscono allo stesso vertice e ogni coppia di vertici distinti ha al massimo un bordo tra loro.
Da questi presupposti, possiamo facilmente mostrare che qualsiasi circuito (indotto o meno) deve contenere almeno tre vertici e almeno tre spigoli. Un circuito con un vertice dovrebbe usare un bordo di loop; un circuito con due vertici dovrebbe riutilizzare un singolo bordo o avere due spigoli tra gli stessi due vertici; ecc.
Ora, dati due circuiti distinti (indotti o meno), questi due circuiti non possono condividere tutti e tre i vertici. Se lo facessero, sarebbero o lo stesso circuito, o ci sarebbero di nuovo due bordi diversi tra la stessa coppia di vertici. Essenzialmente con la stessa logica, qualsiasi due circuiti distinti non può condividere più di un bordo.
Il risultato che circuiti distinti condividono al massimo due vertici e al massimo un bordo implica che per qualsiasi grafico G (V, E), non ci possono essere più di circuiti V-2, e non può esserci più di (E- 1) / 2 circuiti.
Ora posso dimostrare che questo limite superiore non è solo un limite ma anche un massimo presentando un semplice esempio che lo raggiunge. Sia G che contenga i vertici A e B, con il bordo X da A a B. Ci sono attualmente 0 cicli, 2 vertici e 1 bordo. Ora aggiungi un vertice C1, più un bordo Y1 da B a C1 e un altro bordo Z1 da C1 a A. Ora abbiamo 1 ciclo (che è ovviamente indotto), 3 vertici e 3 spigoli. Allo stesso modo, aggiungi il vertice C2 e i bordi Y2 e Z2 in modo da avere 2 cicli indotti, 4 vertici e 5 spigoli. Continua il pattern, e per induzione, quando aggiungiamo CN, YN e ZN, avremo N cicli indotti, 2 + N vertici e 1 + 2N bordi. Ciò significa che N = V-2 e N = (E-1) / 2, che era il nostro limite superiore teorico.
Quindi, il numero massimo di circuiti / cicli indotti in un grafico G (V, E) è il minimo di V-2 e (E-1) / 2.
Leggi altre domande sui tag algorithms graph graph-traversal combinatorics