Costruisci il grafo più piccolo omeomorfo a un dato grafico smussando
La classe dell'omeomorfismo $ \mathcal{H}(G) $ di un grafico $G$ è l'insieme delle classi di isomorfismi dei grafi che sono topologicamente omeomorfi a $G$. È naturale chiedersi: esiste un rappresentante "più piccolo" nella classe dell'omeomorfismo? Se sì, come trovarlo? Sfortunatamente, non ho trovato risultati utili su questo problema dopo una rapida ricerca su Google.
Tuttavia, guidato dall'intuizione, ho la seguente ipotesi:
Il grafico più piccolo omeomorfo di un grafico si ottiene levigando ogni orecchio massimo.
In questo post cerco di abbozzare una dimostrazione, ma c'è una lacuna nella dimostrazione, quindi non so se la mia ipotesi sia effettivamente corretta. Apprezzerei chiunque per sottolineare i miei errori e colmare il vuoto.
Attenzione: questo sarebbe un post lungo
Per prima cosa, chiariamo un po 'di terminologia. Il termine "orecchio" significa cose diverse in diversi libri di testo di teoria dei grafi. In questo post adottiamo la seguente definizione:
Definizione 1
Un orecchio in un grafico può essere:
- un ciclo i cui vertici, tranne forse uno, sono di grado $2$, o
- un percorso i cui vertici interni sono di grado $2$.
Un orecchio massimo è un orecchio che non è un sottografo appropriato di un orecchio più grande. Equivalentemente, un orecchio massimo è uno dei seguenti:
- un ciclo che è di per sé un intero componente connesso
- un ciclo in cui esattamente un vertice è di grado $ \geq 3 $, mentre tutti gli altri vertici sono di grado $2$
- un percorso in cui tutti i vertici interni sono di grado $2$, mentre entrambi i vertici finali sono di grado $ \neq 2 $
Due operazioni comuni che preservano la topologia sui grafici sono la suddivisione e il livellamento:
Definizione 2
Suddividere un bordo significa sostituirlo con un orecchio. Più precisamente, lascia$e = uv$ essere un vantaggio.
Se $u = v$, quindi suddividendo l'auto-loop $e$ significa sostituirlo con un ciclo $C$, e $u = v$ diventa un vertice su $C$, che può avere o meno laurea $2$, a seconda che $e$ è isolato.
D'altra parte, se $u \neq v$, quindi suddividendo $e$ significa sostituirlo con un percorso $P$, e $u, v$ diventano i vertici finali di $P$.
Suddividere un grafico significa preformare una sequenza di suddivisione sui bordi.
Definizione 3
Levigare un orecchio significa sostituirlo con un unico bordo. Più precisamente, lascia$C$ essere un orecchio.
Se $C$ è un ciclo, quindi levigante $C$ significa sostituirlo con un auto-loop $e$e il vertice di grado $ \neq 2 $ su $C$ diventa l'unico vertice incidente su $e$ (se tutti i vertici su $C$ sono di grado $2$, basta scegliere un vertice qualsiasi).
D'altra parte, If $C$ è in realtà un percorso $P$, quindi levigare $P$ significa sostituirlo con un bordo senza loop $e$e i vertici finali di $P$ diventano i vertici finali di $e$.
Levigare un grafico significa preformare una sequenza di levigatura sulle orecchie.
Successivamente, abbiamo il seguente risultato classico sulla topologia dei grafici:
Teorema 1
Due grafici sono omeomorfi se e solo se uno di essi può essere ottenuto da una sequenza di operazioni di suddivisione e livellamento sull'altro.
Prova: vedi questo post .
Teorema 2
Permettere $G$ e $H$essere due grafici omeomorfici. Poi$ |V(G)| = |V(H)| $ se e solo se $ |E(G)| = |E(H)| $.
Schizzo di prova: la suddivisione (o levigatura) aumenta (o diminuisce) sempre il numero di vertici e bordi dello stesso numero.$\square$
Alla luce del Teorema 2, possiamo definire un ordinamento sulla classe dell'omeomorfismo di un grafo:
Definizione 4
Permettere $ \mathcal{H}(G) $ essere la classe di omeomorfismo di un grafico $G$. Definisci l'ordine$\preceq$ su $ \mathcal{H}(G) $ di: $$ G_1 \preceq G_2 \iff |V(G_1)| \leq |V(G_2)| $$ per ogni $ G_1, G_2 \in \mathcal{H}(G) $.
Se $ G_1 \preceq G_2 $ e $ G_2 \preceq G_1 $, quindi indichiamo $ G_1 \sim G_2 $.
L'ordinazione $\preceq$è un preordine totale, il che significa che è transitivo e qualsiasi due grafici omeomorfi sono confrontabili. Purtroppo non è un ordine totale, da allora$ G_1 \sim G_2 $ non implica $ G_1, G_2 $ sono isomorfe, anche attraverso il Teorema 2 implica $ |E(G_1)| = |E(G_2)| $.
Teorema 3
Qualsiasi grafo senza vertice isolato può essere scomposto in modo univoco in un'unione disgiunta di spigoli di spighe massime.
Schizzo di prova:
Permettere $G$essere un grafo senza vertice isolato. Definisci la relazione$R$ su $E(G)$ di: $$ eRf \iff \exists \text{ ear } C \subseteq{G} \text{ s.t. } e, f \in E(C) $$ per ogni $ e, f \in E(G) $.
Poi $R$ è una relazione di equivalenza su $E(G)$, in cui ogni classe di equivalenza contiene i bordi di esattamente un orecchio massimo. Quindi,$R$ induce una decomposizione di $G$in un'unione spigolo-disgiunta delle orecchie massime. Al contrario, una tale decomposizione deve essere indotta da$R$, quindi la scomposizione è unica. $\square$
Sulla base della scomposizione di cui sopra, possiamo definire quanto segue:
Definizione 5
Un grafico senza vertice isolato è detto liscio se ogni orecchio massimo è di lunghezza $1$. Per un grafico$G$ senza vertice isolato, il grafo liscio ottenuto levigando ogni orecchio massimo in $G$ è indicato come $ \text{Smooth} (G) $.
Il termine "grafico uniforme" non è standard, ma non sono riuscito a trovare alcun termine esistente per un tale grafico, quindi lo invento da solo.
Teorema 4
Permettere $G$ essere un grafico regolare senza vertici isolati e $ H \in \mathcal{H}(G) $, poi $ G \preceq H $. Inoltre,$ G \sim H $ se e solo se $H$ è un grafico uniforme.
Schizzo di prova:
Per Teorema 1, $H$ può essere ottenuto da una sequenza di operazioni di suddivisione e lisciatura su $G$. Ogni fase delle operazioni può cambiare solo un orecchio massimo con un altro orecchio massimo di lunghezza possibilmente diversa.
D'altra parte, in un grafico uniforme tutte le orecchie massime hanno già la lunghezza più corta possibile (vale a dire, $1$), quindi qualsiasi sequenza di suddivisione e smussamento non può mai diminuire ulteriormente il numero di vertici. Quindi,$ |V(G)| \leq |V(H)| $ e l'uguaglianza vale se e solo se $H$ è liscia. $\square$
La seguente affermazione si basa sull'intuizione, ma non so come dimostrarlo. È qui che si trova il vuoto di tutta la mia prova.
Richiedi 0
Permettere $G$ e $H$essere due grafici regolari senza vertice isolato. Se sono omeomorfi, allora sono isomorfi.
Infine, assumendo l'affermazione di cui sopra, possiamo dimostrare l'ipotesi principale:
Ipotesi principale
Supponiamo che Claim 0 sia corretto e lascia $G$essere un grafo senza vertice isolato. Poi$ \text{Smooth} (G) $ è l'unico grafico più piccolo in $ \mathcal{H} (G) $ rispetto all'ordinazione $ \preceq $.
Prova:
Il fatto che $ \text{Smooth} (G) \preceq H $ per tutti $ H \in \mathcal{H} (G) $ segue dal Teorema 4.
Per dimostrare l'unicità, lascia $ H \in \mathcal{H} (G) $ essere tale $ \text{Smooth} (G) \sim H $. Da$ \text{Smooth} (G) $ è liscia e $ H \in \mathcal{H} (\text{Smooth} (G)) $, dal Teorema 4, $H$è anche liscia. L'affermazione 0 quindi implica$H$ è isomorfo a $ \text{Smooth} (G) $. $\square$
Domande:
- La richiesta 0 è corretta? Come dimostrarlo?
- Anche se Claim 0 è sbagliata, la mia ipotesi principale è ancora corretta?
- Ci sono altri errori nella mia prova?
- Esiste un termine migliore per i grafici in cui ogni orecchio massimo è di lunghezza $1$, a parte "grafici fluidi"?
Risposte
La tua prova mi sembra corretta. Non vedo perché presumi che il grafo non abbia vertici isolati: fa la differenza ovunque? Inoltre, "grafo liscio" sembra essere un nome di fantasia per un grafo senza vertici di secondo grado. (Più precisamente, gli unici vertici di grado due sono vertici isolati con un ciclo.)
Darò una prova della tua affermazione. Possiamo supporre che i grafici in questione siano connessi e che abbiano almeno un bordo. A qualsiasi grafico$G$, associa un grafico colorato ai vertici $Ear(G)$ nel seguente modo:
- I vertici di $Ear(G)$ corrispondono alle orecchie nella scomposizione unica di $G$nelle orecchie massime. Si colorano di blu e di rosso a seconda che l'orecchio sia un sentiero o un ciclo.
- Due vertici sono adiacenti se le orecchie corrispondenti hanno un vertice comune; se hanno due vertici comuni, allora disegniamo due bordi paralleli. (Questo può accadere solo se le orecchie corrispondenti sono percorsi.)
Ci sono due osservazioni da fare che sono più o meno implicite nella tua dimostrazione del Teorema 4:
- Se $G$ e $H$ sono omeomorfici, quindi $Ear(G)$ e $Ear(H)$sono isomorfe, con l'isomorfismo che preserva i colori dei vertici. Questo segue dal Teorema 1 dopo aver verificato che siano preservati sia lo smussamento che la suddivisione$Ear(G)$.
- Se $G$ è liscia, quindi (ignorando la colorazione) $Ear(G)$è solo il grafico a linee di$G$, definito in modo appropriato per grafici con loop e bordi multipli.
Convenientemente, un teorema di Whitney afferma che se i grafici a linee di due grafici semplici collegati sono isomorfi, i grafici stessi sono isomorfi, a meno che i grafici siano il triangolo$K_3$ e l'artiglio $K_{1,3}$. Nota che il triangolo non è liscio. Nel caso di grafici con loop e bordi paralleli, la situazione è più complicata (anche se non così tanto, secondo questo articolo * a cui ho potuto trovare solo un link protetto da paywall; abbastanza stranamente, il nome di Whitney è scritto male nel titolo) , ma nel nostro caso la colorazione dei vertici e il Teorema 4 ci danno informazioni sufficienti per ricostruire in modo univoco il grafo originale. Probabilmente potresti risolverlo da solo, ma fornirò i dettagli per completezza.
Quindi supponiamo che $G$ e $H$ sono lisci e quello $Ear(G)$ e $Ear(H)$sono isomorfe. Innanzitutto, ci occupiamo dei loop: questi corrispondono proprio ai vertici rossi di$Ear(G)$ e $Ear(H)$. Ne consegue che se indichiamo con$G'$ e $H'$ i grafici ottenuti cancellando i loop in $G$ e $H$, poi $Ear(G')$ e $Ear(H')$ si ottengono cancellando i vertici rossi da $Ear(G)$ e $Ear(H)$; in particolare sono isomorfe. Adesso basta dimostrarlo$G'$ e $H'$ sono isomorfe, poiché allora le posizioni dei loop sono determinate in modo univoco da $Ear(G)$: un vertice in $G'$ ha un ciclo se e solo se c'è un bordo incidente ad esso che è adiacente a un vertice rosso in $Ear(G)$, o se $G'$ consiste in questo singolo vertice (poiché abbiamo assunto che i nostri grafici abbiano almeno un bordo).
Quindi, possiamo presumere che $G$ e $H$non contengono loop. Ora non ci resta che occuparci dei bordi paralleli. Se due bordi sono paralleli in$G$, quindi secondo la nostra costruzione i vertici corrispondenti in $Ear(G)$sono collegati da due bordi paralleli. Più in generale, due o più bordi paralleli in$G$ corrispondono a una cricca in $Ear(G)$in cui ogni bordo è raddoppiato. Ogni vertice in$Ear(G)$ è contenuto in un'unica massima tale "doppia cricca" (potenzialmente di dimensione uno), e contraendo queste cricche e sostituendo i bordi paralleli appena formati con quelli singoli, si ottiene il grafico a linee del grafo semplice sottostante $G$. Poiché funziona anche all'indietro (cioè dal semplice grafico e$Ear(G)$ possiamo riprenderci $G$), possiamo presumere che $G$ e $H$ sono semplici.
Quindi abbiamo finito con il teorema di Whitney, giusto? Beh, non così in fretta. Potrebbe accadere che dopo aver lasciato anelli e bordi paralleli da$G$ e $H$, ci rimane un triangolo e $K_{1,3}$: dopo tutto, un triangolo con bordi raddoppiati è liscio. Ma questo è escluso dal Teorema 4: l'originale$G$ e $H$aveva lo stesso numero di vertici e lasciare i bordi non cambia questo. Così$G$ e $H$ sono davvero isomorfe.
* Si noti che, per quanto ne so, la nozione di grafico a linee usata nell'articolo è diversa da quella usata qui, in quanto i vertici corrispondenti ai bordi paralleli sono ancora collegati con un solo bordo.