Perguntas com a marcação «graph-theory»

10
Diagrama de Voronoi em um gráfico

Seja um gráfico com arestas ponderadas (positivamente). Quero definir o diagrama de Voronoi para um conjunto de nós / sites , para associar a um nó o subgrafo de induzido por todos os nós estritamente mais próximos de do que qualquer outro nó em , medindo o comprimento de um caminho pela soma dos...

10
Amplitude de gráficos cúbicos aleatórios

Considere um gráfico cúbico aleatório conectado devértices, extraídos de reg (como definido aqui , ou seja, é par e quaisquer dois gráficos têm a mesma probabilidade).n = | V | G ( n , 3 ) 3 nG = ( V, E)G=(V,E)G=(V,E)n = | V|n=|V|n =|V|G ( n , 3G(n,3G(n, 3)))3 n3n3n Claro que existem possíveis...

10
Decidindo homomorfismo gráfico

Decidindo o gráfico O homomorfismo é geralmente NP-Completo. Existem resultados que estudam esse problema quando os gráficos subjacentes têm estrutura algébrica (como decidir homomorfismos dos gráficos de cosset de Cayley ou Cayley para outros gráficos com alguma estrutura definida também)? Além...

10
Geração de gráficos de perímetro modo que os ciclos mínimos formem uma cobertura de borda dupla

Seja . Preciso gerar gráficos simples de circunferência modo que o conjunto de todas as -cycles forme uma cobertura de borda dupla de (ou seja, toda aresta é compartilhada por exatamente duas -cycles), e de modo que a interseção de duas -cycles é um vértice, uma aresta ou vazio. Os gráficos gerados...

10
Árvores abrangentes

Uma árvore de abrangência de um gráfico é chamada de árvore de completude se o conjunto de folhas induzir um subgráfico completo no gráfico do host. Dado um gráfico e um número inteiro , qual é a complexidade de decidir se contém uma árvore de completude com no máximo folhas?k G kGGGkkkGGGkkk Uma...

9
A fonte do gráfico de decomposição modular

Ao introduzir a decomposição modular do gráfico , a maioria dos autores usa o gráfico de 11 vértices, que eu copio da wikipedia. A questão é quem é (é) o criador original dele. (Não estou perguntando quem desenhou este gráfico para a wikipedia, mas a fonte original dele.) A página da wikipedia...

9
Número de ciclos em um gráfico

Quantos ciclos CkCkC_k (k≥3)(k≥3)(k \geq 3) existem em um gráfico de nnn vértices, de modo que o gráfico não possua nenhum ciclo CmCmC_m (m>k)(m>k)(m>k) . Por exemplo n=5n=5n=5 , k=3k=3k=3 , em seguida gráfico terá no máximo dois C3C3C_3 's de modo a que GGG não terá...