Considere um gráfico com todas as arestas com capacidade unitária. Pode-se encontrar o corte mínimo no tempo polinomial. Suponha que eu possa aumentar a capacidade de qualquer arestas até o infinito (equivalente a mesclar os nós em ambos os lados da aresta). Qual é a maneira ideal de selecionar um...
O teorema de Robertson-Seymour diz que qualquer de gráficos de família menos fechada pode ser caracterizado por finitos muitos menores proibidos.GG\mathcal G Existe um algoritmo que para uma entrada gera os menores proibidos ou isso é indecidível?GG\mathcal G Obviamente, a resposta pode...
Estou tentando encontrar um gráfico com essas propriedades para meus estudos, mas infelizmente não consigo encontrar esse gráfico. Alguém sabe se existe esse gráfico ou por que é impossível
Estou resolvendo um problema de "mesclar" conjuntos de imagens sobrepostas. Esses conjuntos podem ser representados por gráfico ponderado não direcionado, como este: Cada nó representa uma imagem. Imagens sobrepostas são conectadas por uma borda. O peso da borda representa o tamanho da área de...
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á...
Temos o algoritmo para determinar se um gráfico tem um ciclo de comprimento exatamente . Como podemos descobrir quantas dessas motocicletas estão presentes em usando o mesmo ou qualquer outro algoritmo. G k k Gf( k ) n3f(k)n3f(k)
Suponha que eu tenha conjuntos com elementos extraídos de possíveis. Cada conjunto é do tamanho ( ), onde os conjuntos podem se sobrepor. Quero determinar se os dois problemas a seguir estão completos ou não com NP:r n n <
Dada uma linguagem regular no alfabeto , seu autômato determinístico mínimo pode ser visto como um gráfico múltiplo direcionado com constante grau externoe um estado inicial marcado (esquecendo rótulos de transições, estados finais). Mantemos o estado inicial porque cada vértice deve ser acessível...
Verificar a transitividade de um dígrafo não é mais fácil do que (em termos de complexidade assintótica) fazer o fechamento transitivo do dígrafo? Conhecemos algum limite inferior melhor que para determinar se um dígrafo é transitivo ou
Houve algumas perguntas ( 1 , 2 , 3 ) sobre a conclusão transitiva aqui que me fizeram pensar se algo como isso é possível: Suponha que obtemos um gráfico direcionado para entrada e gostaríamos de responder a perguntas do tipo " ?", Ou seja, perguntando se existe uma aresta entre dois vértices...
Problema clássico: Seja dado um número . O problema da classe é o seguinte.kkkkkk Dado um gráfico , existe um subconjunto de vértices para que quaisquer dois vértices de sejam adjacentes?GGGSSSkkkSSS Problema do hipergrafo: Seja dado os números e . O problema -hiperclique é o...
Estou procurando referências para o seguinte problema: dados inteiros nnn e kkk , enumere todos os gráficos planares não isomórficos em nnn vértices e largura de árvore ≤k≤k\leq k . Eu estou interessado tanto em resultados teóricos e práticos, mas principalmente algoritmos práticos que são...
Esta pergunta é dupla e é principalmente orientada a referências: Existe algum lugar onde as principais intuições para provar o teorema menor do gráfico são dadas, sem entrar muito nos detalhes? Sei que a prova é longa e difícil, mas certamente deve haver idéias-chave que possam ser comunicadas...
Sejam GGG e HHH dois gráficos conectados em rrr de tamanho . Vamos ser o conjunto de permutações P tal que P L P - 1 = H . Se L = H então Um é o conjunto de automorphisms de L .nnnAAAPPPPGP−1=HPGP−1=HPGP^{-1}=HG=HG=HG=HAAAGGG Qual é o limite superior mais conhecido no tamanho de AAA ? Existem...
Dado um gráfico e a alguém deseja calcular . ( ) A `` expansão em pequenos conjuntos conjectura "afirma que é NP-Difícil determinar se isso está abaixo de ou acima de paraδ > 0 h ( G , δ ) = m i n | S | ≤ δ | V | ϕ ( S ) ϕ ( S ) = E ( S , ˉ S )G=(V,E)G=(V,E)G=(V,E)δ>0δ>0\delta >...
Seja um gráfico. Um conjunto vértice X ⊆ V é chamado crítico se X ≠ ∅ e nenhum vértice em V ∖ X é adjacente a exatamente um vértice em X . O problema é encontrar um conjunto vértice S ⊆ V de tamanho mínimo de tal modo que S ∩ X ≠ ∅ para cada conjunto crítico X .G=(V,E)G=(V,E)G=(V,E)X⊆VX⊆VX\subseteq...
Seja um gráfico que seja a união disjunta de um clique e um conjunto independente, ou seja, GGGG = Kn1 1+ Kn2¯¯¯¯¯¯¯¯= Kn1 1+ In2.G=Kn1 1+Kn2¯=Kn1 1+Eun2.G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . A classe de gráficos de todos esses gráficos é caracterizada pelos subgráficos induzidos...
Considere o seguinte problema: Entrada: um gráfico simples (não direcionado) .G=(V,E)G=(V,E)G=(V,E) Pergunta: Existe uma orientação do satisfazendo a propriedade que, para cada s , t ∈ V existe no máximo um (dirigida) s - t caminhada?GGGs,t∈Vs,t∈Vs,t \in Vsssttt Isso pode ser equivalente...
Gostaria de saber se o seguinte problema é NP-difícil. Insira: G = ( V, E)G=(V,E)G = (V,E) um gráfico simples e uma coloração f: E→ { 1 , 2 , 3 }f:E→{1 1,2,3}f : E \to \{1,2,3\} das arestas ( fff não verifica nenhuma propriedade específica). Pergunta: é possível particionar EEE em | E| /...
É agora uma observação bem conhecida que muitas estruturas gráficas que surgem em ambientes naturais tendem a obedecer a propriedades sem escala, como a lei de potência da distribuição de graus. Existe algum bom exemplo de gráficos naturais bastante aleatórios e que não necessariamente obedeçam...