Ad alte temperature le foreste bruciano... e poi?
Ad alte temperature le foreste bruciano... e poi?
Vorrei trovare tutti i grafi G tali che ogni grafo di grado minimo sufficientemente grande contiene un sottografo uguale a G... chi mi da una mano?
scusa edriv che forse è una domanda idiota: che cos 'è il grado di un grafo?è il numero di lati? poichè vorrei pensare al problema che poni..vorrei essere sicuro di pensare al problema che poni..grazie e scusa
Ciao!
Ciao!
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Il grado di un nodo del grafo è il numero di lati che partono da quel nodo.
Se un grafo ha grado minimo 4, ad esempio, vuol dire che da ogni nodo partono almeno 4 lati (e c'è un nodo da cui partono esattamente 4 lati, altrimenti il grado minimo sarebbe superiore).
Tanto vale che definisco bene tutto allora.
Dati due grafi H,G, un morfismo di grafi da H a G è una funzione f dai vertici di H ai vertici di G tale che, se a,b sono vertici di H collegati da un lato, anche f(a) ed f(b), che sono vertici di G, sono collegati da un lato.
Allora chiedo di trovare tutti i grafi H per cui esiste un k tale che:
se G è un grafo con grado minimo maggiore o uguale a k, allora esiste un morfismo iniettivo da H in G.
Se un grafo ha grado minimo 4, ad esempio, vuol dire che da ogni nodo partono almeno 4 lati (e c'è un nodo da cui partono esattamente 4 lati, altrimenti il grado minimo sarebbe superiore).
Tanto vale che definisco bene tutto allora.
Dati due grafi H,G, un morfismo di grafi da H a G è una funzione f dai vertici di H ai vertici di G tale che, se a,b sono vertici di H collegati da un lato, anche f(a) ed f(b), che sono vertici di G, sono collegati da un lato.
Allora chiedo di trovare tutti i grafi H per cui esiste un k tale che:
se G è un grafo con grado minimo maggiore o uguale a k, allora esiste un morfismo iniettivo da H in G.
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Intanto G dev'essere una foresta: per un famoso teorema di Erdos, esistono grafi con girth arbitrariamente alto e numero cromatico arbitrariamente alto. Una facile conseguenza è che questi grafi contengono sottografi che hanno grado minimo arbitrariamente alto. E naturalmente, il girth di un sottografo non può diminuire.
Dimostrare che tutte le foreste vanno bene, è un facile esercizio: si fissi un insieme di alberi (radicati), si prenda un grafo di grado minimo sufficientemente alto, e si costruisca ogni albero a partire dalla radice, e andando avanti livello per livello... A voi i dettagli!
Dimostrare che tutte le foreste vanno bene, è un facile esercizio: si fissi un insieme di alberi (radicati), si prenda un grafo di grado minimo sufficientemente alto, e si costruisca ogni albero a partire dalla radice, e andando avanti livello per livello... A voi i dettagli!
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Comunque adesso siamo sicuri del claim: i grafi sono tutte e sole le foreste. La dimostrazione di Erdos usa una tecnica probabilistica, ma non la definirei non elementare. Forse esiste una scorciatoia per il grado minimo anziché il numero cromatico, perché apparentemente il problema è più semplice (dire che un grafo è localmente un albero forza il suo numero cromatico locale a 2, ma non dice nulla sul grado minimo locale).
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12