Grafi planari
Spero sia la sezione giusta, se non lo fosse chiedo scusa...
Dato un grafo $G$, per dire se è planare o meno basta vedere se contiene (almeno) una clique di grado $5$ o (almeno) un sottografo bipartito completo tre per tre.
Quello che mi chiedo è: a partire da un grafo, per decidere se è planare o no, può essere usata solo questa procedura o esistono altri algoritmi?
Dato un grafo $G$, per dire se è planare o meno basta vedere se contiene (almeno) una clique di grado $5$ o (almeno) un sottografo bipartito completo tre per tre.
Quello che mi chiedo è: a partire da un grafo, per decidere se è planare o no, può essere usata solo questa procedura o esistono altri algoritmi?
Risposte
Dato un grafo $G$ di ordine $p$ e taglia $q$, una condizione necessaria per la planarità è: $q<=3p-6$.
In parole povere: se ci sono troppi lati, il grafo non può essere planare. L'uguaglianza è verificata nel caso in cui $G$ sia planare massimale.
Spero che questo ti sia di aiuto, se mi viene in mentre qualcos'altro ti faccio sapere.
Non ero a conoscenza del criterio sul sottografo bipartito tre per tre da te citato, grazie per l'informazione. Se hai voglia mi dai una traccia della sua dimostrazione?
In parole povere: se ci sono troppi lati, il grafo non può essere planare. L'uguaglianza è verificata nel caso in cui $G$ sia planare massimale.
Spero che questo ti sia di aiuto, se mi viene in mentre qualcos'altro ti faccio sapere.
Non ero a conoscenza del criterio sul sottografo bipartito tre per tre da te citato, grazie per l'informazione. Se hai voglia mi dai una traccia della sua dimostrazione?
Non ho una dimostrazione, ho solo dato un'occhiata su Wikipedia (Th. di Kuratowski). 
Comunque grazie.
Comunque grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo