Grafo semplice non orientato e insiemistica

locke1
si consideri il grafo semplice non orientato in cui i vertici sono i numeri naturali di 5 cifre (in base 10) con cifre scelte fra 3,4,5,6 e in cui due vertici distinti x,y sono adiacenti se il prodotto della prima cifra di x e della cifra di y è>15.
Qunate componenti connese ha il grafo?
Qual'e' il numero cromatico del grafo?
dopo avere calcolato il grado di tutti i vertici del grafo, verificare e in ogni componente (considerata come grafo a sè stante estite un cammino ciclico eurleriano.


risolvo:
il vertice numero 6 è adiacente con tutti gli altri vertici, quindi il grafo ha una solo componente connessa.
il numero cromatico del grafo del vertice 6 è 4^4, poiche' deve averetutti colori diversi
il numero cromatico del vertice 4 che e' adiacente con il vertice 5 (perche' 5x4=20>15) è 4^2
piche' i gradi dei vertici sono entrambia pari, esiste una cammino ciclico euleriano.






siano A un insieme di cardinalita' 9 e b un sottoinsieme di A di cardinalita' 3. Calcolare:
a) il numero dei sottoinsiemi C di A di cardinalita' pari che contengono b come sottoinsieme
b) il numero dei sottoinsiemi non vuoti del prodotto cartesiano AxB che abbiano cardinalita <4


risolvo:
per costruire ogni sottoinsieme C di a, bisogna guardare la cardinalita di b (deve contenere b come sottoinsime) ed esso si puo' fare in $ ( ( ( ( <6> , <3> ) ) ) ) $ modi diversi.
per costruire il numero dei sottoinsimei non vuoti del prodotto cartesiano AxB che abbiano cardinalita' <4, si puo' procedere in questa maniera.
Si possono costruire 9 sottoinsiemi di cardinalita' 3 (9x3=27) oppure 27 sottoinsiemi di cardinalita' 1.

grazie per eventuali risposte dettagliate sui miei eventuali sbagli.

Risposte
Rggb1
"locke":
il vertice numero 6 è adiacente con tutti gli altri vertici, quindi il grafo ha una solo componente connessa.

Se i vertici sono i numeri di 5 cifre (34566, 35645...) [ovvero il grafo ha 4^5 nodi], quale sarebbe il vertice "numero 6"?

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.