Quanti sono i possibili grafi distinti con N vertici?
Buongiorno,
è possibile calcolare il numero di grafi distinti che è possibile ottenere avendo N vertici?
Grazie in anticipo!
è possibile calcolare il numero di grafi distinti che è possibile ottenere avendo N vertici?
Grazie in anticipo!
Risposte
Sì basta contare i possibili archi e ricordare che per ogni arco ci sono 2 possibilità (esserci o non esserci). Ti lascio dedurre la formula.
"Martino":
Sì basta contare i possibili archi e ricordare che per ogni arco ci sono 2 possibilità (esserci o non esserci). Ti lascio dedurre la formula.
Allora in un grafo con 5 vertici possono esserci al massimo 8 lati,dopodichè il primo grafo avrà 8 lati,il secondo 7 ecc..è corretto?
Però al di fuori del grafo completo,possono esserci 8 grafi da 7 lati,8 da 6 ecc..corretto?
Falla più semplice. Supponi di avere 3 vertici. Quanti grafi riesci a costruire?
4?
Non mi risulta. Comunque non è un quiz 
è per farti ragionare, se pensi che siano 4 allora dimmi quali sono questi 4.
è per farti ragionare, se pensi che siano 4 allora dimmi quali sono questi 4.
Credo siano i seguenti,scusami la scarsa precisione:
[/url]
[/url]
E quelli con un solo arco? E quelli senza archi?
Quindi contanto anche quello senza archi e con un solo arco,avremmo 4 + 1 + 3?
Sì quindi 8 in totale. Adesso riesci a generalizzare?
[(2*NUMERO VERTICI)+2]? Se si,mi potrei inviare un link riguardo tale teoria/dimostrazione?
No stai sparando a caso (senza offesa). Prova a scrivere qualcosa di ragionato e ti risponderò.
Allora abbiamo detto che con tre vertici abbiamo 8 possibili grafi,4 dei quali connessi,3 composti da un solo arco ed 1 composto da nessun arco con 3 vertici isolati.
Sappiamo che in un grafo la somma dei gradi di tutti i vertici è uguale a 2 x (NUMERO DEI LATI),sapendo che la somma dei gradi di tutti i vertici in un grafo a tre vertici è 6(ogni vertice ha grado 2),sappiamo che il numero dei lati è 3. Ogni lato può "apparire o meno" dunque stiamo a 2 x 3, a cui va sommato il grafo completo(+1) e quello senza archi (+1). Cosa ne pensi?
Sappiamo che in un grafo la somma dei gradi di tutti i vertici è uguale a 2 x (NUMERO DEI LATI),sapendo che la somma dei gradi di tutti i vertici in un grafo a tre vertici è 6(ogni vertice ha grado 2),sappiamo che il numero dei lati è 3. Ogni lato può "apparire o meno" dunque stiamo a 2 x 3, a cui va sommato il grafo completo(+1) e quello senza archi (+1). Cosa ne pensi?
"Ogni vertice ha grado due" in generale è falso.
Guarda è molto semplice.
Hai $n$ vertici. Quindi [tex]\binom{n}{2}[/tex] possibili archi.
Ogni arco può esserci o no. Quindi abbiamo [tex]2^{\binom{n}{2}}[/tex] possibili grafi.
Guarda è molto semplice.
Hai $n$ vertici. Quindi [tex]\binom{n}{2}[/tex] possibili archi.
Ogni arco può esserci o no. Quindi abbiamo [tex]2^{\binom{n}{2}}[/tex] possibili grafi.
Per quanto riguarda la combinazione semplice per ricavare il numero di archi,tutto bene.
Non capisco il perchè utilizzare la disposizione con ripetizione,uno stesso arco non può essere ripetuto nello stesso sottoinsieme di K elementi,perchè non utilizzare la disposizione semplice? Cosa mi sfugge?
Non capisco il perchè utilizzare la disposizione con ripetizione,uno stesso arco non può essere ripetuto nello stesso sottoinsieme di K elementi,perchè non utilizzare la disposizione semplice? Cosa mi sfugge?
Non capisco cosa intendi con "disposizione con ripetizione".
Domanda 1. Sei d'accordo che il numero di archi possibili è [tex]\binom{n}{2}[/tex]?
Domanda 2. Sei d'accordo che il numero di grafi possibili è [tex]2^{\binom{n}{2}}[/tex]?
Cerca di essere chiaro/a nelle risposte.
Domanda 1. Sei d'accordo che il numero di archi possibili è [tex]\binom{n}{2}[/tex]?
Domanda 2. Sei d'accordo che il numero di grafi possibili è [tex]2^{\binom{n}{2}}[/tex]?
Cerca di essere chiaro/a nelle risposte.
Si scusami,allora sono d'accordo la con la prima,ma non capisco il perchè della seconda. Supponendo di avere tre vertici di nome A - B - C,con la la prima avremmo AB - AC - BC che sono i tre lati. Ma nella seconda quali sottoinsieme di K elementi avremmo? Perchè utilizzare la disposizione con ripetizione?
Nella seconda sto dicendo che ogni arco può esserci oppure non esserci. Quindi 2 elevato al numero di archi.
Se preferisci posso dirlo anche in questo modo: nella seconda sto contando il numero di modi in cui posso scegliere un qualsiasi insieme di archi. Il numero di archi è [tex]m=\binom{n}{2}[/tex]. Un insieme con $m$ elementi ha esattamente $2^m$ sottoinsiemi.
Se preferisci posso dirlo anche in questo modo: nella seconda sto contando il numero di modi in cui posso scegliere un qualsiasi insieme di archi. Il numero di archi è [tex]m=\binom{n}{2}[/tex]. Un insieme con $m$ elementi ha esattamente $2^m$ sottoinsiemi.
Perfetto,quindi i sottoinsiemi dell'insieme del numero di archi,rappresentano i vari grafi. Per quanto riguarda la disposizione con ripetizione, credevo l'avessi utilizzata ma mi sbagliavo,hai semplicemente applicato la teoria riguardo il numero dei sottoinsiemi in un insieme con M elementi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo