Teoria dei grafi: esercizio su grafo connesso
Ciao ragazzi,
ho trovato questo esercizio a cui ho provato a dare risposta, ma non mi è chiaro se va bene o no.
Sia G un grafo connesso avente i vertici tutti di grado pari. Si provi che scelto comunque uno spigolo $ e \in E(G)$ il grafo ottenuto da G cancellando lo spigolo e resta connesso.
La risposta che mi è venuta in mente è:
Data la definizione di grafo conesso che dice: un grafo si dice connesso quando dati 2 vertici qualunque v e w esiste un percorso da v a w, direi che il grafo dell'esercizio, sì, resta connesso perchè se nel grafo il numero minimo di archi che parte da un vertice è 2 e vado a togliere un arco (o spigolo) il vertice rimarrà collegato al grafo dall'altro arco. Quindi il grafo continuerà ad essere connesso.
è giusto poter dire così???
ho trovato questo esercizio a cui ho provato a dare risposta, ma non mi è chiaro se va bene o no.
Sia G un grafo connesso avente i vertici tutti di grado pari. Si provi che scelto comunque uno spigolo $ e \in E(G)$ il grafo ottenuto da G cancellando lo spigolo e resta connesso.
La risposta che mi è venuta in mente è:
Data la definizione di grafo conesso che dice: un grafo si dice connesso quando dati 2 vertici qualunque v e w esiste un percorso da v a w, direi che il grafo dell'esercizio, sì, resta connesso perchè se nel grafo il numero minimo di archi che parte da un vertice è 2 e vado a togliere un arco (o spigolo) il vertice rimarrà collegato al grafo dall'altro arco. Quindi il grafo continuerà ad essere connesso.
è giusto poter dire così???
Risposte
"duombo":Purtroppo no perché dire che "il vertice rimarrà collegato al grafo dall'altro arco" non basta per concludere che "dati 2 vertici qualunque v e w esiste un percorso da v a w".
Data la definizione di grafo conesso che dice: un grafo si dice connesso quando dati 2 vertici qualunque v e w esiste un percorso da v a w, direi che il grafo dell'esercizio, sì, resta connesso perchè se nel grafo il numero minimo di archi che parte da un vertice è 2 e vado a togliere un arco (o spigolo) il vertice rimarrà collegato al grafo dall'altro arco. Quindi il grafo continuerà ad essere connesso.
è giusto poter dire così???
Segue la mia risposta al quesito che hai posto.
Supponi per assurdo che togliendo un lato [tex]e[/tex] al tuo grafo lo sconnetti in due pezzi, chiamiamoli A e B (li puoi vedere naturalmente come sottografi di G). Allora A e B sono connessi (se uno dei due fosse sconnesso allora è facile vedere che anche G sarebbe sconnesso). Il vertice di A che è estremo del lato [tex]e[/tex] si ritrova in A ad avere grado uno di meno del suo grado in G, in particolare dispari, mentre ogni altro vertice di A ha lo stesso grado di prima (è collegato solo a vertici di A, altrimenti G sarebbe connesso, essendo A e B connessi), in particolare pari. E la somma di un dispari con tanti pari è un numero dispari. Ma questo contraddice il fatto ben noto che la somma dei gradi dei vertici di un grafo è uguale al doppio del numero di spigoli, in particolare è un numero pari.
Grazie mille Martino,
quindi se ho ben capito non posso dire che se tolgo uno spigolo il vertice rimane connesso dall'altro arco, perchè andrei contro il th che mi dice che il numero di spigoli di un grafo è il doppio della somma dei gradi dei vertici, ma a questo punto non saprei come rispondere a questo quesito
tu come risponderesti?
quindi se ho ben capito non posso dire che se tolgo uno spigolo il vertice rimane connesso dall'altro arco, perchè andrei contro il th che mi dice che il numero di spigoli di un grafo è il doppio della somma dei gradi dei vertici, ma a questo punto non saprei come rispondere a questo quesito
tu come risponderesti?
No non ci siamo capiti, nel mio intervento precedente rispondo alla tua domanda "è giusto poter dire così???" quando dico
Quello che segue nel mio intervento, cioè quello che comincia con "Supponi per assurdo" e che finisce con "in particolare è un numero pari." è esattamente la mia risposta al quesito che hai posto all'inizio.
Ciao
"Martino":
"Purtroppo no perché dire che "il vertice rimarrà collegato al grafo dall'altro arco" non basta per concludere che "dati 2 vertici qualunque v e w esiste un percorso da v a w"."
Quello che segue nel mio intervento, cioè quello che comincia con "Supponi per assurdo" e che finisce con "in particolare è un numero pari." è esattamente la mia risposta al quesito che hai posto all'inizio.
Ciao
ok Martino, grazie mille... guardando bene la teoria penso di aver capito anche meglio la tua risposta... ora è tutto più chiaro
continuando a fare esercizi su grafi e alberi, ne ho trovato uno che dice
"Esiste un albero avente 24 vertici, di cui almeno 2 di grado 2, almeno 3 di grado 3 e almeno 4 di grado 4?"
La mia risposta è stata: no.
il motivo è che la somma dei vertici che mi da la traccia è 29 $(2*2+3*3+4*4)$ che è maggiore di 24 quindi un albero descritto in quel modo non esiste.
Va bene una risposta del genere secondo te?
grazie mille
continuando a fare esercizi su grafi e alberi, ne ho trovato uno che dice
"Esiste un albero avente 24 vertici, di cui almeno 2 di grado 2, almeno 3 di grado 3 e almeno 4 di grado 4?"
La mia risposta è stata: no.
il motivo è che la somma dei vertici che mi da la traccia è 29 $(2*2+3*3+4*4)$ che è maggiore di 24 quindi un albero descritto in quel modo non esiste.
Va bene una risposta del genere secondo te?
grazie mille
Purtroppo no perché la somma delle valenze dei vertici è uguale al doppio del numero dei lati e non ti basta il numero di vertici per concludere.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo