Che materia stai cercando?

Strutture geometriche e algebriche - dimostrazione della condizione necessaria per un grafo G connesso Appunti scolastici Premium

Appunti per l'esame di strutture geometriche, prof. Giorgio Donati, con la dimostrazione della condizione necessaria per un Grafo G connesso, con varie dimostrazioni, formule e procedure tramite ipotesi induttive e figure esplicative del grafo e dei procedimenti

Esame di Strutture geometriche e algebriche docente Prof. G. Donati

Anteprima

ESTRATTO DOCUMENTO

Dimostrazione della condizione necessaria per un Grafo G connesso:

Dimostriamo che ⇒

= ≥ −

G grafo connesso con V (

G ) n E (

G ) n 1

Si usa l’induzione! = =

Dimostriamo che è vero nel caso , caso base (il caso è caso banale quindi passiamo a

n 2 n 1

= ).

n 2

Evidentemente è vero perché avremo soltanto 2 nodi e un lato (di sicuro perché è connesso) come

nella figura seguente: = ≥ − = − = quindi è vera.

Infatti in tal caso E (

G ) 1 n 1 2 1 1 ∈

v V (G ) la

Adesso prima di procedere con l’ipotesi induttiva supponiamo di prendere un vertice

= ≤ ≤ −

d ( v ) k

cui valenza sia (dove visto che G è connesso e quindi il vertice al limite sarà

1 k n 1

collegato ad uno solo degli altri vertici oppure a tutti gli altri ) e stacchiamolo dal grafo G. Così

n-1

di componenti connesse , ,..., . Si vede che risulta

facendo otteniamo un certo numero G G G

l 1 2 l

≤ ≤ =

. Precisamente otterremo una sola componente connessa ( ) quando tutti gli altri vertici

1 l k l 1

distinti da erano comunque collegati tra loro come in figura:

v

v

[Con il tratteggio indico gli spigoli che vengono eliminati eliminando il vertice ]

v

componenti connesse nel caso in cui era collegato ad altri nodi (a loro volta

Invece avremo k v k

eventualmente collegati ad altri ma non tra di loro) e li teneva uniti tipo il centro di una stella come

nella seguente figura: v …

= ≥ −

. Per ipotesi induttiva possiamo affermare che

Sia allora ( ) ( ) 1

n V G E G n

i i i i


PAGINE

2

PESO

36.54 KB

AUTORE

Menzo

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Menzo di informazioni apprese con la frequenza delle lezioni di Strutture geometriche e algebriche e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof Donati Giorgio.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Strutture geometriche e algebriche

Strutture geometriche e algebriche - esercizi
Esercitazione
Strutture geometriche e algebriche - esercizi
Esercitazione
Strutture geometriche e algebriche - esercizi
Esercitazione
Strutture geometriche e algebriche - Esercitazione
Esercitazione