Questions marquées «graph-theory»

Je veux être très précis. Quelqu'un connaît-il un rejet ou une preuve de la proposition suivante: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in...

Étant donné un graphe orienté avec n nœuds tels que chaque sommet a exactement deux bords sortants, et un nombre naturel N codé en binaire, deux sommets s et t, Je veux compter le nombre de chemins (pas nécessairement simples) de s à t dans N étapes. Est-ce un problème # P-difficile? Ou...

Nous savons par exemple de Koutis-Miller-Peng (basé sur les travaux de Spielman & Teng), que nous pouvons résoudre très rapidement des systèmes linéaires pour les matrices qui sont la matrice de graphes laplaciens pour certains graphes clairsemés avec des poids de bord non négatifs .Ax=bAx=bA x...

Soit C4C4C_4 un cycle à quatre sommets. Pour un graphe arbitraire GGG avec nnn sommets et m arêtes disons m>nn−−√m>nnm>n\sqrt n , combien deC4C4C_4existent? Y a-t-il une limite inférieure pour

Ici: http://www.planarity.org/Klein_elementary_graph_theory.pdf (dans le chapitre plongements) est donnée la définition de l' intégration combinatoire d'un graphe planaire. (avec définition des faces, etc.) Bien qu'il puisse être facilement utilisé pour n'importe quel graphe, ils définissent le...

Il y a eu quelques efforts pour attaquer le problème d'isomorphisme des graphes en utilisant la marche aléatoire quantique des bosons à noyau dur (symétrique mais sans double occupation). La puissance symétrique de la matrice d'adjacence, qui semblait prometteuse, s'est révélée incomplète pour les...

Il est formulé en étendant les graphiques de seuil . Étant donné un graphique de seuil où C est la clique et I est l'ensemble indépendant, mon extension est la suivante: Chaque sommet v ∈ I peut être remplacé par une nouvelle clique K v de telle sorte que les sommets de K v aient le mêmes voisins...

Dans le célèbre contre-exemple de l'isomorphisme des graphes via la méthode de Weisfeiler-Lehman (WL), le gadget suivant a été construit dans cet article par Cai, Furer et Immerman. Ils construisent un graphe donné parXk= ( Vk, Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk= Ak∪ Bk∪ Mk où UNEk= { aje∣ 1 ≤ i ≤ k...

Disons qu'une famille de graphes a de longs chemins induits s'il y a une constante telle que chaque graphe dans contient un chemin induit sur sommets. Je m'intéresse aux propriétés des familles de graphes qui assurent l'existence de longs trajets induits. En particulier, je me demande actuellement...

Dans un graphique, un ensemble indépendant est un sous-ensemble de sommets qui ne contient pas d'arête comme sous-graphique induit. Le problème de trouver les plus grands ensembles indépendants dans un graphique est une question algorithmique fondamentale, et difficile à résoudre. Considérons la...

Cela peut ressembler davantage à une question de sciences sociales qu'à une question TCS, mais ce n'est pas le cas. En lisant " Algorithmes randomisés " qui décrit le problème du mariage stable, on peut lire ce qui suit (p54) "On peut montrer que pour chaque choix de listes de préférences, il...

Cela m'embrouille. Un cas facile de comptage est lorsque le problème de décision est en et qu'il n'y a pas de solutions.PPP Une conférence montre que le problème du comptage du nombre de correspondances parfaites dans un graphique bipartite (de manière équivalente, le comptage du nombre de...

Crossposted de MO . Soit une classe de graphes définie par un nombre fini de sous-graphes induits interdits, tous cycliques (contenant au moins un cycle).CCC Existe-t-il des problèmes de graphes NP-difficiles qui peuvent être résolus en temps polynomial pour autre que Clique et Clique cover?CCC Si...

Je voudrais savoir s'il existe un résultat déjà publié à ce sujet: Nous prenons tous les chemins différents possibles entre chaque paire de nœuds de deux graphiques réguliers connectés (avec le degré disons et le nombre de nœuds ) et notons leurs longueurs. Bien sûr, ce nombre de chemins distincts...

Je voudrais savoir si le problème suivant peut être résolu dans (espace de log non déterministe):N LNL\mathsf{NL} Étant donné un graphe orienté avec deux sommets distincts s et t , existe- t -il un chemin unique de s à t dans G ?GGGssstttssstttGGG Je pense qu'il est susceptible d'être dans car nous...

Supposons que nous ayons un semi-groupe avec les éléments . Notre objectif est de calculer les produits .S = { s 1 , s 2 , … , s n } s i ∘ s i + 1 ∘ ⋯ ∘ s j( S, ∘ )(S,∘)(S,\circ)S= { s1, s2, … , Sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesje∘ si + 1∘ ⋯ ∘ sjsje∘sje+1∘⋯∘sjs_i\circ...

Rappelons le diamètre d'un graphe est la longueur d'un plus court chemin plus long . Étant donné un graphique, un algorithme évident pour calculer résout le problème du chemin le plus court toutes paires (APSP) et renvoie la longueur du chemin le plus long trouvé.G diam ( G )gGGgGGdiam ( G...

Le théorème de Courcelle stipule que chaque propriété de graphe définissable en logique monadique du second ordre peut être décidée en temps linéaire sur des graphes de largeur d'arbre bornée . C'est l'un des méta-théorèmes algorithmiques les plus connus. Motivé par le théorème de Courcelle, j'ai...

Que sait-on actuellement de l'approximation du problème du genre? Une recherche préliminaire m'indique qu'une approximation à facteur constant est triviale pour des graphes suffisamment denses, et un algorithme d'approximation a été exclu. Ces informations sont-elles à jour ou existe-t-il de...

Relâchons un peu la coloration, c'est-à-dire que nous permettons à un petit nombre de sommets adjacents de se voir attribuer la même couleur. Un composant monochromatique est défini comme étant un composant connecté dans le sous-graphique induit par l'ensemble de sommets qui reçoivent la même...