Teoria dei grafi
Salve ragazzi in pratica oggi il nostro professore ha spiegato la teoria dei grafi.
dicendo che un grafo semplice è una coppia (V,L) dove V è un insieme non vuoto, mentre
L è un sottoinsieme di P2(V) ovvero un sottoinsieme dell insieme delle parti formato da esattamente due elementi di V, ho capito bene è esatto??
anche se però non capisco non sarebbe piu corretto scrivere L appartiene a P2(V) invece di scrivere che è un sottoinsieme di P2(V)??
inoltre un altra domanda per grafo completo ho questa definizione:
se e solo se
L=P(V) cosa vuol dire questa cosa??
grazie
dicendo che un grafo semplice è una coppia (V,L) dove V è un insieme non vuoto, mentre
L è un sottoinsieme di P2(V) ovvero un sottoinsieme dell insieme delle parti formato da esattamente due elementi di V, ho capito bene è esatto??
anche se però non capisco non sarebbe piu corretto scrivere L appartiene a P2(V) invece di scrivere che è un sottoinsieme di P2(V)??
inoltre un altra domanda per grafo completo ho questa definizione:
se e solo se
L=P(V) cosa vuol dire questa cosa??
grazie
Risposte
allora un grafo è tale che G = (V,E) dove V sono i nodi e E sono gli archi.
metti di avere un grafo (abbi un po' di fantasia XD) fatto in questo modo
.-.-.-.
allora sono presenti 4 nodi, due di grado 1 (sono "toccati" da un solo arco ciascuno) e due di grado 2 (quelli centrali, sono "toccati" da due archi ciascuno).
Allora si può dire che è un grafo, perchè l'equazione
$\sum_{v in V} d(v) = 2 |E|$
è verificata, infatti d(v) (dove v appartiene a V, naturalmente) è la somma di tutti i gradi dei nodi di G. Quindi 1+2+2+1 = 6. gli archi (le linee) quanti sono? 3. Infatti l'equazione è verificata, perchè come puoi notare subito(sostituendo a d(v) 6, e ad |E| 3),
6 = 2*3
ora provo a rispondere alle tue domande. probabilmente 2P(v) corrisponde al mio 2 |E|, che è l'insieme degli archi. moltiplicato per due (quindi 2P(V)) è uguale a L, che è l'insieme dei vertici (il mio d(v)). Utilizzo una notazione diversa, ma i concetti sono gli stessi. Se leggi bene la mia risposta, dovresti trovare la soluzione che cerchi
metti di avere un grafo (abbi un po' di fantasia XD) fatto in questo modo
.-.-.-.
allora sono presenti 4 nodi, due di grado 1 (sono "toccati" da un solo arco ciascuno) e due di grado 2 (quelli centrali, sono "toccati" da due archi ciascuno).
Allora si può dire che è un grafo, perchè l'equazione
$\sum_{v in V} d(v) = 2 |E|$
è verificata, infatti d(v) (dove v appartiene a V, naturalmente) è la somma di tutti i gradi dei nodi di G. Quindi 1+2+2+1 = 6. gli archi (le linee) quanti sono? 3. Infatti l'equazione è verificata, perchè come puoi notare subito(sostituendo a d(v) 6, e ad |E| 3),
6 = 2*3
ora provo a rispondere alle tue domande. probabilmente 2P(v) corrisponde al mio 2 |E|, che è l'insieme degli archi. moltiplicato per due (quindi 2P(V)) è uguale a L, che è l'insieme dei vertici (il mio d(v)). Utilizzo una notazione diversa, ma i concetti sono gli stessi. Se leggi bene la mia risposta, dovresti trovare la soluzione che cerchi
ok senti un altra cosa sto studiando il cammino in un grafo..
vorrei solo sapere una cosa un arco o lato di un grafo viene considerato un cammino?
ed inoltre gli estremi(ossia i due vertici) di un arco sono anche connessi?
poiche c ho scritto che due vertici si dicono connessi se sono congiunti da un cammino..
sono vere queste mie affermazioni??
grazie
vorrei solo sapere una cosa un arco o lato di un grafo viene considerato un cammino?
ed inoltre gli estremi(ossia i due vertici) di un arco sono anche connessi?
poiche c ho scritto che due vertici si dicono connessi se sono congiunti da un cammino..
sono vere queste mie affermazioni??
grazie
dato un grafo G = (V,E) un cammino è una successione di vertici di V (v0,v1,v2,....,vk) tale che vi, vi+1 è un arco. (per 0$ \leq $ i $ \leq $ k-1).
Se (v0,v1,v2,....,vk) è un cammino, diciamo che v0 congiunge vk.
Data la definizione di cammino, un arco viene considerato un cammino, da un vertice di partenza v0 a un vertice di arrivo v1.
Gli estremi di un arco sono connessi per definizione, è abbastanza intuibile. Se fai due puntini su un foglio e li unisci con una riga, sono connessi? Direi di si, non ci piove
Alla tua ultima domanda ho già risposto con la seconda...Spero di esser stato chiaro
Se (v0,v1,v2,....,vk) è un cammino, diciamo che v0 congiunge vk.
Data la definizione di cammino, un arco viene considerato un cammino, da un vertice di partenza v0 a un vertice di arrivo v1.
Gli estremi di un arco sono connessi per definizione, è abbastanza intuibile. Se fai due puntini su un foglio e li unisci con una riga, sono connessi? Direi di si, non ci piove
Alla tua ultima domanda ho già risposto con la seconda...Spero di esser stato chiaro
@Black27 & Leonardo20: Sarebbe l'ora di imparare ad inserire le formule col MathML (almeno... Cfr. regolamento, 3.6b).
i minori uguali li ho messi...ora edito subito anche con la sommatoria sorry ma non sapevo come metterla e ho avuto poco tempo per rispondere! Ora edito...
P.S. i grafi non so come rappresentarli con LaTex
/fine OT
sorry ma non sapevo come metterla e ho avuto poco tempo per rispondere! Ora edito...P.S. i grafi non so come rappresentarli con LaTex
/fine OT
@Black27: Grazie.
Occhio, però, anche ai vettori, apici e pedici, etc...
Per i grafi lascia stare: non so nemmeno se è installato qualche pacchetto apposito del TeX (né saprei come usarne qualcuno, dato che non ho mai avuto l'occasione d'imparare).
Occhio, però, anche ai vettori, apici e pedici, etc...
Per i grafi lascia stare: non so nemmeno se è installato qualche pacchetto apposito del TeX (né saprei come usarne qualcuno, dato che non ho mai avuto l'occasione d'imparare).
Per i grafi si puo' usare il xymatrix. Esempio:
[tex]\xymatrix{& & \ast \ar@{-}[dl] \ar@{->}[dr]_{\partial} & & \\ & \ast \ar@{<-}[dr]^{x} \ar@{->}[dl] & & \ast \ar@{-}[dl] \ar@{<--}[dr] & \\ \ast \ar@{-}[dr]^{\oplus} & & \ast \ar@{-}[dr]^Y \ar@{<..}[dl]_{\otimes} & & \ast \ar@{->}[dl]^{\times} \\ & \ast \ar@{-}[dr] & & \ast \ar@{-}[dl]_{\rtimes} & \\ & & \ast & &}[/tex] [tex]\xymatrix{& & \ast \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] & & \\ & \ast \ar@{-}[dl] \ar@{<-}[dr] & \ast \ar@{--}[dll] \ar@{-->}[drr] & \ast \ar@{-}[dl] \ar@{-}[dr] & \\ \ast \ar@{-}[drr] & & \ast \ar@{-}[d] & & \ast \ar@{->}[dll] \\ & & \ast & & }[/tex] [tex]\xymatrix{& & \ast \ar[d] & \ast \ar[d] & \ast \ar[d] & & \\ & & \ast \ar[d] \ar[r] & \ast \ar[d] \ar[r] & \ast \ar[d] \ar `r[rr] `[dd] `^d[llll] `[dddd] [ddddll] & & \\ & & \ast \ar[dd] \ar[r] & \ast \ar[dd] \ar[r] & \ast \ar[dd] \ar[r] & \ast & \\ & & & & & & \\ & \ast \ar[r] & \ast \ar[d] \ar[r]^{mani} & \ast \ar[d] \ar[r]^{comio} & \ast \ar[d] & & \\ & & \ast \ar[r] \ar[d] & \ast \ar[d] \ar[r] & \ast \ar[d] & & \\ & & \ast & \ast & \ast & & }[/tex]
Il terzo e' in onore del lemma del serpente
[tex]\xymatrix{& & \ast \ar@{-}[dl] \ar@{->}[dr]_{\partial} & & \\ & \ast \ar@{<-}[dr]^{x} \ar@{->}[dl] & & \ast \ar@{-}[dl] \ar@{<--}[dr] & \\ \ast \ar@{-}[dr]^{\oplus} & & \ast \ar@{-}[dr]^Y \ar@{<..}[dl]_{\otimes} & & \ast \ar@{->}[dl]^{\times} \\ & \ast \ar@{-}[dr] & & \ast \ar@{-}[dl]_{\rtimes} & \\ & & \ast & &}[/tex] [tex]\xymatrix{& & \ast \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] & & \\ & \ast \ar@{-}[dl] \ar@{<-}[dr] & \ast \ar@{--}[dll] \ar@{-->}[drr] & \ast \ar@{-}[dl] \ar@{-}[dr] & \\ \ast \ar@{-}[drr] & & \ast \ar@{-}[d] & & \ast \ar@{->}[dll] \\ & & \ast & & }[/tex] [tex]\xymatrix{& & \ast \ar[d] & \ast \ar[d] & \ast \ar[d] & & \\ & & \ast \ar[d] \ar[r] & \ast \ar[d] \ar[r] & \ast \ar[d] \ar `r[rr] `[dd] `^d[llll] `[dddd] [ddddll] & & \\ & & \ast \ar[dd] \ar[r] & \ast \ar[dd] \ar[r] & \ast \ar[dd] \ar[r] & \ast & \\ & & & & & & \\ & \ast \ar[r] & \ast \ar[d] \ar[r]^{mani} & \ast \ar[d] \ar[r]^{comio} & \ast \ar[d] & & \\ & & \ast \ar[r] \ar[d] & \ast \ar[d] \ar[r] & \ast \ar[d] & & \\ & & \ast & \ast & \ast & & }[/tex]
Il terzo e' in onore del lemma del serpente
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo