Топ-100
Indietro

ⓘ Grafo semplice. Si dice grafo semplice un grafo non diretto che non comprende cappi e archi multipli. I grafi semplici sono logicamente equivalenti alle relazio ..




Grafo semplice
                                     

ⓘ Grafo semplice

Si dice grafo semplice un grafo non diretto che non comprende cappi e archi multipli.

I grafi semplici sono logicamente equivalenti alle relazioni simmetriche antiriflessive. Quindi la matrice delle adiacenze di un grafo semplice è una matrice binaria simmetrica avente nulle tutte le entrate della diagonale principale. Viceversa, ogni matrice di questo tipo rappresenta un grafo semplice.

Di solito per grafo semplice si intende un grafo finito, cioè un grafo che presenta un insieme finito di nodi. Talora possono essere utili anche grafi semplici infiniti.

Gran parte delle teoria dei grafi non orientati riguarda i grafi semplici: infatti per molte proprietà dei grafi la presenza di cappi o di archi multipli non ha alcuna influenza. Questo accade ad esempio per proprietà come raggiungibilità, esistenza di cammini hamiltoniani, colorabilità, planarità e connettività dei diversi tipi. Allopposto, i problemi riguardanti i cammini euleriani riguardano naturalmente grafi che presentani spigoli multipli o digrafi che presentano archi multipli.

Coerentemente, quasi tutte le applicazioni dei grafi non orientati ad altre questioni matematiche si servono di grafi semplici. Ad esempio, sono grafi semplici i grafi associati ai poliedri. Per la classificazione delle algebre di Lie semisemplici servono invece grafi con spigoli multipli, come i diagrammi di Coxeter-Dynkin.

                                     
  • grafo non orientato, sprovvisto di cappi si dice grafo semplice Lo scheletro sk G di G è il grafo che si ottiene da G eliminandone tutti i cappi e sostituendone
  • anche per i poliedri semplici Questa non è una coincidenza: ogni poliedro semplice può essere trasformato in un grafo semplice connesso usando i vertici
  • stesso grafo Se le coppie di nodi si considerano ordinate il grafo è detto orientato o digrafo, altrimenti non orientato o semplice Il grafo è detto
  • incidenti con esso. Esistono molti sinonimi di grafo ciclo Questi comprendono grafo ciclo semplice e grafo ciclico, sebbene il secondo termine sia usato
  • Un grafo G è una coppia V, E dove V è un insieme e E V V è un sottoinsieme del prodotto cartesiano di V per se stesso. Gli elementi di V sono detti
  • superficie S è un piano si parla di raffigurazione piana del grafo Due raffigurazioni di un grafo sopra una superficie si dicono topologicamente equivalenti
  • arco Il duale di un grafo planare G è un grafo planare G che può avere cappi e multiarchi anche se G era semplice Se G è un grafo connesso e G è il
  • dei grafi un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino grafo non orientato, connesso e
  • matematica e algoritmica della teoria dei grafi, il grafo trasposto di un digrafo G è un altro grafo orientato definito sullo stesso insieme di nodi in
  • compresi il grafo dei servizi, il grafo di Petersen, il grafo di Heawood, il grafo di Möbius - Kantor, il grafo di Pappus, il grafo di Desargues, il grafo di Nauru
  • dell architettura del Web semantico, dove un insieme di dichiarazioni RDF un grafo sono identificate utilizzando un URI, rendendo così possibili descrizioni
  • di grado 2 scelti in modo da mantenere il carattere di grafo semplice si individua un grafo K con due vertici di grado 3 e due di grado 2, dal quale
  • matematico della teoria dei grafi, il grafo di Petersen è un grafo non orientato con 10 vertici e 15 spigoli. È un piccolo grafo che serve come utile esempio e