Esercizi su grafi, alberi e matrici di adiacenza.

[lapoalberto77]

Salve,

ho eseguito questi esercizi e mi piacerebbe sapere se sono corretti.
Altri hanno anche la soluzione ma non corrispondono a quello che ho fatto io e vorrei sapere dove ho sbagliato.
Spero possiate cortesemente aiutarmi.

Esercizio 1)
Si scriva la matrice di adiacenza del grafo seguente. Esso è planare? è bipartito?


risolvendo l'esercizio
la matrice di adiacenza dovrebbe essere la seguente:
$((0,1,1,1,1,0),(1,0,0,0,1,1),(1,0,0,1,0,1),(1,0,1,0,1,0),(1,1,0,1,0,1),(0,1,1,0,1,0))$

>alla domanda "è planare?"
considero la definizione di planare:
Un grafo $G$ si dice planare se può essere disegnato su un piano senza incroci.

ho tenuto conto del seguente teorema:
teorema di Kuratowski:
Un grafo finito $G$ è planare se e solo se non contiene nessun sottografo che sia contraibile per archi a $K_5$ o a $K_(3,3)$

dò inoltre la definizione di sottografo:
Un sottografo di un grafo $G$ è un grafo che ha tutti i vertici e tutti gli archi in $G$.

quindi dico che "sì, è planare" perchè
se considero il sottografo risultante rimuovendo il vertice $5$ e i relativi archi ottengo il seguente, che può essere disegnato senza incroci:


>alla domanda "è bipartito?"
rispondo no, perchè se considero il seguente
teorema:
Un grafo è bipartito se e solo se non contiene alcun ciclo dispari.

se consideriamo il ciclo $1,5,4,1$ esso ha lunghezza 3, $\Rightarrow$ è un ciclo dispari $\Rightarrow$ non è bipartito.
è corretto il ragionamento?


esercizio 2)
Tutti i vertici di un grafo $G$ hanno grado $>= 2$. Si provi che allora il grafo contiene almeno un ciclo.

ecco il grafo che ho considerato:

tutti i vertici hanno grado $>= 2$ e per esempio il percorso $v_1, v_3, v_2, v_1$ è un ciclo di lunghezza 3.


esercizio 3)
Può esistere un albero in cui due vertici hanno grado 2, tre hanno grado 3, quattro hanno grado 4 e tutti gli altri hanno grado 1? Se sì, quanti vertici in tutto deve avere?
io ho risposto sì, 22 vertici totali. Ho considerato il seguente grafo e a fianco di ogni vertice ho scritto il suo grado:



poi ho questi due esercizi di cui posto sia il mio svolgimento sia la soluzione scritta sul libro, le quali però non coincidono. perchè?
esercizio 4)
ho il seguente grafo. determinare la matrice di adiacenza:


la matrice che ho scritto io è la seguente:
$((1,1,1,0),(1,1,0,1),(1,0,1,1),(0,1,1,1))$
mentre la matrice sul libro è la seguente:
$((1,1,0,1),(1,1,1,0),(0,1,1,1),(1,0,1,1))$

qual è quella sbagliata?


esercizio 5)
determinare la matrice di adiacenza del seguente grafo orientato:


la matrice che ho scritto io è la seguente:
$((0,0,1,0),(1,0,0,1),(0,0,0,1),(0,0,0,0))$
mentre la matrice sul libro è la seguente:
$((0,1,0,0),(0,0,1,0),(0,0,0,0),(1,0,1,0))$

anche qui qual è quella sbagliata? perchè non coincidono?


se avete letto fin qui davvero mille grazie.
spero possiate darmi un vostro aiuto
saluto tutti e ancora mille grazie.

[Martino]

Ciao!

Ecco le mie osservazioni sulle tue argomentazioni.

"lapoalberto77":quindi dico che "sì, è planare" perchè
se considero il sottografo risultante rimuovendo il vertice $5$ e i relativi archi ottengo il seguente, che può essere disegnato senza incroci

Non mi pare un argomento valido. Il fatto che quel sottografo sia planare non implica che il grafo originario sia planare.

esercizio 2)
Tutti i vertici di un grafo $G$ hanno grado $>= 2$. Si provi che allora il grafo contiene almeno un ciclo.

ecco il grafo che ho considerato:

Ma tu non devi dare un esempio di grafo che verifica l'asserto, devi dimostrare l'asserto. Cioè consideri un grafo (finito, altrimenti è falso) ogni cui vertice abbia grado almeno 2 e dimostri che deve esistere un ciclo.

Quanto alle matrici di adiacenza, sia le tue che quelle della soluzione vanno bene, avete solo ordinato i vertici in modi diversi.

[lapoalberto77]

Non mi pare un argomento valido. Il fatto che quel sottografo sia planare non implica che il grafo originario sia planare.

Facendo lo stesso lavoro anche sugli altri sottografi anch'essi risultano planari.
E comunque non credo di avere altri elementi sul mio testo. Ho qui una
Proposizione:
Sia $G$ un grafo semplice, connesso e planare con $n$ vertici e $m$ archi. Valgono le seguenti implicazioni:
1. Se $n >= 3$ allora $m <= 3n - 6$.
2. Se $n > 3$ e non ci sono cicli di lunghezza 3, allora $m <= 2n - 4$.

questa però è una condizione necessaria ma non sufficiente.
E c'è anche un'altra frase: "L'importante è capire che se un grafo rispetta i due criteri detti non possiamo concludere che è planare".
E comunque attenendomi alla proposizione nel grafo considerato esiste un ciclo di lunghezza 3.
Quindi che significa che non è planare? Quali sono altri metodi per determinare subito la planarità di un grafo?

consideri un grafo (finito, altrimenti è falso) ogni cui vertice abbia grado almeno 2 e dimostri che deve esistere un ciclo.

Considerando il grafo dell'esercizio 2 che ho fatto io per avere un riferimento grafico, è giusto dire che se non c'è alcun ciclo il grafo diventa un albero?

[Martino]

"lapoalberto77":Quali sono altri metodi per determinare subito la planarità di un grafo?

Cercando di vederlo a occhio. Il grafo dell'esercizio 1 è planare, prova a dimostrarlo.

Considerando il grafo dell'esercizio 2 che ho fatto io per avere un riferimento grafico, è giusto dire che se non c'è alcun ciclo il grafo diventa un albero?

Non capisco la domanda. Nel grafo che hai disegnato per l'esercizio 2 ci sono cicli. Tieni presente che la definizione di albero è "grafo connesso non orientato e senza cicli".

[lapoalberto77]

Riguardo l'esercizio 1, non ho idea di come dimostrarlo.
Riguardo l'esercizio 2 penso si debba aplicare la dimostrazione del teorema di eulero per i grafi euleriani.
Teorema di Eulero per i grafi euleriani:
Un grafo $G$ privo di vertici isolati è euleriano se e solo se
a) è connesso;
b) il grado do ogni vertice di $G$ è un numero pari;

[Martino]

"lapoalberto77":Riguardo l'esercizio 1, non ho idea di come dimostrarlo.

Spostando i vertici in modo opportuno. L'ho fatto prima, non serve usare teoremi complicati, è un esercizio da settimana enigmistica.

Riguardo l'esercizio 2 penso si debba aplicare la dimostrazione del teorema di eulero per i grafi euleriani.

Io avevo in mente di fare così: prendi un certo vertice 1. Prendi un vertice 2 a cui è collegato. Dal vertice 2 parte almeno un altro arco (perché i vertici hanno grado almeno 2), quindi il vertice 2 è collegato ad un altro vertice, chiamiamolo 3. 3 è collegato a un vertice 4, e così via. Siccome il grafo è finito seguendo questo procedimento otterrò una ridondanza, che corrisponderà evidentemente ad un ciclo nel grafo.

[Rggb1]

1) mi sembra tu abbia già risposto: per verificare la planarità di un grafo puoi:
- verificare direttamente se sia rappresentabile;
- applicare il teorema di Kuratowsky, ovvero verificare tutti i sottografi;
- applicare l'inverso, ovvero verificare se ha un sottografo omeomorfo a $K_5$ o $K_(3,3)$ e concludere che non è planare.

2) secondo me sei vicino: devi dimostrare che un grafo, se ha tutti i vertici di grado pari o superiore a 2, ha almeno un ciclo. Per assurdo, se così non fosse, sarebbe un albero; quali proprietà ha un grafo ad albero?

[Rggb1]

"Martino":... è un esercizio da settimana enigmistica.

L'ho vista adesso

[lapoalberto77]

per l'esercizio 1 è questo?


(Rggb non ridere delle disgrazie altrui )

[Rggb1]

Non ridevo di te, comunque. E poi te l'ho detto che avevi già risposto

Riguardo il (2) anche la dimostrazione di Martino mi sembra carina, io però pensavo al fatto che un albero ha una semplice proprietà: il numero degli spigoli è uguale al numero dei vertici più uno...