Топ-100
Indietro

ⓘ Grafo dintervallo. Nella teoria dei grafi, un grafo dintervallo è il grafo dintersezione di un multiinsieme di intervalli sulla linea reale. Ha un solo vertice ..




Grafo dintervallo
                                     

ⓘ Grafo dintervallo

Nella teoria dei grafi, un grafo dintervallo è il grafo dintersezione di un multiinsieme di intervalli sulla linea reale. Ha un solo vertice per ciascun intervallo dellinsieme, e uno spigolo tra ogni coppia di vertici corrispondenti agli intervalli che intersecano.

                                     

1. Definizione

Sia { I 1, I 2., I n } ⊂ P R un insieme di intervalli.

Il grafo dintervallo corrispondente è G = V, E, dove

  • { I α, I β } ∈ se e solo se I α ∩ I β ≠ ∅.
  • V = { I 1, I 2., I n }, e

Da questa costruzione si può verificare una proprietà comune posseduta da tutti i grafi dintervallo. Ossia, il grafo G è un grafo dintervallo se e solo se le cricche massimali di G si possono porre nellordine M 1, M 2., M k tale che per un qualsiasi v ∈ M i ∩ M k, dove i

                                     
  • un grafo d intervallo è appunto un insieme di intervalli non sovrapposti. Il problema di trovare insiemi indipendenti massimi nei grafi d intervallo è
  • Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più
  • La scomposizione ad albero di un grafo è anche l albero di giunzione dell algoritmo omonimo. I grafi d intervallo sono i grafi d intersezione di sottoalberi
  • qualsiasi insieme indipendente massimale in un unico vertice. Un grafo d intervallo è un grafo le cui cricche massimali possono essere ordinate in modo tale
  • struttura del grafo Per esempio, quando si assegnano gli aeromobili ai voli, il grafo dei conflitti risultante è un grafo d intervallo così il problema
  • Neo4j è un software per basi di dati a grafo open source sviluppato interamente in Java. È un database totalmente transazionale, che viene integrato nelle
  • aspetti combinatori degli insiemi indipendenti massimali di vertici in un grafo Per altri aspetti degli insiemi indipendenti di vertici nella teoria dei
  • colorazione dei vertici di un grafo formata da un algoritmo goloso greedy algorithm che considera i vertici del grafo in sequenza e assegna a ciascun
  • F È semplice vedere che un matroide è anche un greedoide intervallo Si consideri un grafo indiretto G. Sia l insieme base formato dagli archi di G
  • diciamo di voler trovare la massima foresta di copertura di un grafo Ovvero, dato un grafo e un peso per ogni arco, trovare una foresta contenente ogni
  • topologica e di Hausdorff quindi coincidono per gli spazi vettoriali reali. Un grafo avente un numero finito di vertici e spigoli ha dimensione topologica 1