Skip to content

Existe-t-il un graphe non singulier pour lequel le déterminant de sa matrice d'adjacence reste le même lors de la suppression d'un sommet ?

Ne cherchez plus partout sur internet puisque vous êtes tombé sur le bon espace, nous avons la solution que vous cherchez et sans vous compliquer la tâche.

Solution :

Il existe un graphe simple $G=(V,E)$ accompagné d'un sommet $vin V$ tel que $operatorname{det}(A(G))$ et $operatorname{det}left(A(Gbackslash{v})right)$ sont égaux et non nuls.

Exemple. On sait que le déterminant de la matrice d'adjacence du graphe complet $K_n$ est $(-1)^{n-1}(n-1)$. Soit $G'=K_5$ le graphe complet sur l'ensemble des sommets $.[1,5]$. Par la remarque précédente $operatorname{det}(A(G'))=4$. Supposons que $G$ soit obtenu à partir de $G'$ en ajoutant un sommet $0$ et deux arêtes $(0,1)$ et $(0,2)$.

Soit $E_{0,0}$ la matrice $6times 6$ indexée par $.[0,5]times [0,5]$ avec une entrée $1$ à $(0,0)$ et des zéros sinon. Alors la matrice

begin{align*}
A(G)-E_{0,0}=left(begin{matrix}
-1&1&1&0&0&0
1&0&1&1&1&1
1&1&0&1&1&1
0&1&1&0&1&1
0&1&1&1&0&1
0&1&1&1&1&0
end{matrix}right)
end{align*}

est singulier car $(2,1,1,-1,-1,-1)^T$ est un vecteur propre avec une valeur propre de $0$. Par conséquent,
begin{align*}
0=operatorname{det}(A(G)-E_{0,0})=operatorname{det}(A(G))-operatorname{det}(A(G')),
end{align*}
de sorte que $operatorname{det}(A(G))=operatorname{det}(A(G'))=4$.

Proposition. L'unique plus petit graphe w.r.t. nombre d'arêtes de la sorte demandée est.

enter image description here (Ce graphe est isomorphe au graphe n°126 ci-dessous).

Il a $6$ sommets et $8$ arêtes.
Le déterminant de sa matrice d'adjacence est égal à $-4$. En supprimant l'unique sommet de degré-deux avec deux voisins de degré-trois (en bas sur l'image), on obtient un graphe dont la matrice d'adjacence a un déterminant de $-4$, également.

Parmi les 156 types d'isomorphisme de graphes à 6$-vertex, le seul autre graphe du type demandé par le PO est le graphe trouvé par Philipp Lampe à 2018-03-05 18:38:11Z, soit ,

enter image description here,

(ce graphe est isomorphe au graphe n° 116 ci-dessous).

et il n'existe pas d'exemple sur cinq sommets ou moins.

Le graphe ci-dessus a $6$ sommets et $12$ arêtes. De ce fait, la réponse à 2018-03-05 18:38:11Z a fourni un exemple du type demandé avec. le plus petit nombre possible de sommets mais a manqué l'exemple du plus petit nombre de bords (par quatre arêtes). ${}i1}Espaces{}{}125pt}$ Fin de la proposition.

Sur le contenu de cette réponse.

Contenu. Cette réponse contient

1. une preuve de la proposition (en supposant que Sage dise la vérité),

2. une correction de deux erreurs dans un tableau dans l'article publié suivant (qui est très pertinent pour la question du PO) :

[A2012] Alireza Abdollahi, Déterminants des matrices d'adjacence des graphes., Transactions on Combinatorics, vol. 1, n° 4 (2012), p. 9-16.

Notation. Par souci de brièveté, tout au long, 'a.d. (d'un graphe $G$)' est un raccourci pour l'expression beaucoup plus longue 'déterminant de la matrice d'adjacence (d'un graphe $G$)'. (L'abréviation "a.d." signifie "déterminant d'adjacence").

Sur les illustrations . Chacune des captures d'écran de la sortie Sage ci-dessous est donnée dans une résolution suffisante pour que tous les chiffres soient visibles (il faudra peut-être zoomer ou cliquer sur l'image).

J'ai trafiqué les images de la sortie de diverses manières pour les rendre plus utiles (en particulier, la valeur de l'a.d. est surlignée en bleu), mais seulement dans la mesure où cela était faisable en un temps supportable. En particulier, j'ai fait pas en aucune façon essayé d'améliorer le dessin des graphiques de Sage. Je ne comprends pas le raisonnement qui sous-tend l'ordre dans lequel les graphiques sont répertoriés par Sage, et je ne l'ai pas non plus modifié. Le fait de ne pas interférer avec cet ordre rend les données plus reproductibles. Les chiffres bleus, que j'ai ajoutés, donnent l'ordre dans lequel les graphiques ont été crachés par Sage.

Détails.

Je commence par le point 2. ci-dessus, car il est utile d'avoir ce tableau à disposition pour une double vérification ultérieure.

Sur le point 2. Le tableau incorrect est le suivant :

enter image description here
(source : [A2012; p. 11]; annotations added; le cadre cyan autour de l'url est dans l'original)

Les lignes marquées comme fausses sont certainement fausses, peu importe que Sage soit correct ou non. J'ai vérifié cela soigneusement, et je donnerai les raisons ci-dessous (en bref, les lignes marquées en rouge peuvent être vues comme fausses à partir des exposants/multiplicités seuls, sans tenir compte des valeurs).

Les lignes marquées 'vérifié avec Sage' sont probablement correctes, puisque j'ai pu reproduire chacune d'entre elles avec le code Sage suivant.(*):

g=graphes(9)
v=list(g)

len(v)

résultats=[]

pour i dans l'intervalle(274668) :

$hspace{10pt}$ results.append(v[i].adjacency_matrix().det())

from collections import defaultdict

histo = defaultdict(int)

pour k dans les résultats :

$hspace{10pt}$ histo[k] += 1

histo

(ici 'histo' est pour 'histogramme')(**)) à la suite de quoi la sortie suivante est produite :

defaultdict(, {0 : 133174, -128 : 2, 2 : 6767, 4 : 6950,
6 : 4669, 8 : 1566, 10 : 1349, 12 : 1156, 14 : 695, 16 : 606, 18 : 106, 20 :
297, 22 : 173, 24 : 240, 26 : 95, 28 : 91, 30 : 61, 32 : 46, 34 : 5, 36 : 32,
38 : 28, 40 : 3, 64 : 1, 42 : 17, 44 : 16, 54 : 3, -72 : 12, 60 : 3, -64 : 7,
-96 : 3, -60 : 5, -56 : 17, -54 : 12, -50 : 27, -48 : 13, -46 : 20, -44 : 39,
-42 : 47, -40 : 103, -38 : 52, -36 : 110, -34 : 128, -32 : 593, -30 : 199, -28 :
295, -26 : 392, -24 : 765, -22 : 579, -20 : 869, -18 : 2747, -16 : 2247, -14 :
1805, -12 : 3062, -10 : 4290, -8 : 17582, -6 : 8531, -4 : 14901, -2 : 57065})

J'ai annoté le tableau de diverses manières ; en particulier, j'ai déplacé les entrées de la ligne pour $n=6$ un peu vers la gauche pour faire de la place à ce que je considère être les valeurs correctes. (Incidemment, la seule erreur dans [A2012] pour cette ligne est le multiplicité de la valeur de l'a.d.-4$.; le reste de cette ligne est correct. La multiplicité de $4$ est $5$, et non $2$ comme indiqué dans le tableau).

Comment prouver que les lignes pour $n=5$ et $n=6$ sont fausses ? Cela découle déjà de la somme des exposants. Inutile de préciser que pour chaque ligne, la somme des exposants doit être égale au nombre de classes d'isomorphisme (aka nombre de graphes non étiquetés) des graphes avec ce nombre de sommets. D'après A000088 et un tableau à la page 105 de [Flajolet-Sedgewick, Analytic Combinatorics, CUP, version 26 June 2009],

  • sur $3$ sommets, il y a $4$ classes d'isomorphisme de graphes,
  • sur 4$ sommets, il y a $11$ classes d'isomorphisme de graphes,
  • sur $5$ sommets, il y a $34$ classes d'isomorphisme de graphes,
  • sur $6$ sommets, il y a $156$ classes d'isomorphisme de graphes,
  • sur $7$ sommets, il y a $1044$ classes d'isomorphisme de graphes,
  • sur $8$ sommets, il y a $12346$ classes d'isomorphisme de graphes,
  • sur $9$ sommets, il y a $274668$ classes d'isomorphisme de graphes,

alors que

  • dans le rang pour $n=3$, la somme des multiplicités est de $3+1=4,$.

    ce qui est cohérent,

  • dans la ligne pour $n=4$, la somme des multiplicités est $1+7+3=11,$.

    ce qui est cohérent,

  • dans la ligne pour $n=5$, la somme des multiplicités est $1+25+6+1=33,$.

    qui contredit le nombre $34$ ci-dessus,

  • dans la ligne pour $n=6$, la somme des multiplicités est $3+5+32+99+10+2+2=153,$.

    qui contredit le nombre $156$ ci-dessus,

  • dans la ligne pour $n=7$, la somme des multiplicités est de 2+2+13+21+20+690+204+40+17+25+5+5 = 1044,$.

    ce qui est cohérent,

  • dans le rang pour $n=8$, la somme des multiplicités est $2+2+5+5+7+21+51+43+90+79+128+251+581+813+6551+2416+758+240+73+139+24+23+32+8+1+3=12346,$.

    ce qui est cohérent,

  • dans le rang pour $n=9$, la somme des multiplicités est $2+3+12+7+5+17+12+27+13+20+39+47+103+52+110+128+593+199+295+392+765+579+869+2747+2247+1805+3062+4290+17582+8531+14901+57065+133174+6767+6950+4669+1566+1349+1156+695+606+106+297+173+240+95+91+61+46+5+32+28+3+17+16+3+3+1=274668, $

    ce qui est cohérent.

En outre,

Sur le point 1. A prouver la proposition, on note d'abord qu'il est évident qu'il n'existe pas d'exemple sur trois sommets ou moins.

Maintenant, nous montrons qu'il existe aucun exemple sur quatre sommets.
Pour cela, on note d'abord que les seuls graphes sur trois sommets sans sommets isolés (et donc ayant une chance quelconque d'aboutir à un a.d. non nul) sont .

  • le chemin, à trois sommets dont l'a.d. est de $0$, et

  • le triangle, avec un a.d. de 2$.

Ainsi, les seuls candidats de graphes à quatre sommets du type demandé par le PO sont ceux dont l'a.d. vaut $2$. Maintenant, le code de Sage

pour G dans les graphes(4) :

$hspace{10pt}$ print([G.adjacency_matrix(),G.adjacency_matrix().det(),G.show()])

a produit la sortie suivante :

enter image description hereenter image description hereenter image description here

et cela montre qu'il n'existe pas de graphe à quatre sommets avec un a.d. de $2$. (Cela est également corroboré par la ligne pour $n=4$ dans le tableau de la section [A2012; p. 11].) Ceci complète la preuve qu'il n'existe pas d'exemple à quatre sommets.

Nous montrons maintenant qu'il y a aucun exemple sur cinq sommets. A la fois d'après la sortie Sage ci-dessus, et d'après le tableau en [A2012] nous voyons que les seules valeurs non nulles de l'AD sur quatre sommets sont $1$ et $-3$. Par conséquent, les seuls candidats pour un exemple à cinq sommets sont les graphes à cinq sommets dont l'écart-type est de $1$ ou $-3$. Maintenant, le code Sage

pour G dans graphes(5) :

$hspace{10pt}$ print([G.adjacency_matrix(),G.adjacency_matrix().det(),G.show()])

a produit la sortie suivante :

enter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description here

Tant ce qui précède, que le tableau dans [A2012; p. 11]suggèrent fortement que il n'existe pas de graphe sur cinq sommets avec un a.d. égal à $-3$ ou $1$. Si c'est vrai (ce qui semble très probable au vu de [A2012] qui déclare avoir utilisé $textsf{GAP}$, un logiciel différent de Sage), cela implique qu'il n'existe effectivement pas d'exemple à cinq sommets. Inutile de préciser qu'il ne s'agit pas d'une proo mathématique.f; Malheureusement, je ne peux pas imaginer comment on pourrait donner une preuve qui soit meilleure que l'inspection de toutes les instances, même en utilisant une formule "combinatoire" bien connue pour les déterminants d'interprétation trouvée dans.[H1962; p. 208]Cette formule implique toujours des sommets positifs et négatifs, c'est pourquoi je ne pense pas qu'elle mérite d'être considérée comme une interprétation véritablement combinatoire (c'est plus un jugement esthétique, bien sûr). L'interprétation de Harary jusqu'à présent ne semble pas aider à résoudre le problème ouvert, et elle n'offre aucun avantage computationnel.

Nous prouvons maintenant que sur six sommets il y a exactement deux exemples du type demandé par l'OP. Des 34 graphes présentés ci-dessus, il résulte que très probablement les seules valeurs d'a.d. non nulles sur cinq sommets sont $-4$, $-2$, $2$, $4$. Donc, le seuls candidats pour des exemples du type demandé sur six sommets sont ceux qui ont ces valeurs de l'écart-type. Maintenant, le code Sage

pour G dans les graphes(6) :

$hspace{10pt}$ print([G.adjacency_matrix(),G.adjacency_matrix().det(),G.show()])

a produit la sortie suivante. Les mêmes remarques que ci-dessus s'appliquent en ce qui concerne la présentation. En particulier, le fait que je n'aie pas amélioré le dessin des graphiques est plus évident ici, car, dans plusieurs cas, comme les graphiques n° 114, et 184 (et plus particulièrement les n° 105 et 114), le dessin des graphiques n'a pas été amélioré. 114 et 184 (et plus particulièrement les graphiques 105 et 114, dont les bords sont presque invisibles), les "choix" artistiques de Sage n'étaient pas si sages que cela. La plupart du temps, cependant, Sage s'est remarquablement bien débrouillé pour dessiner les graphiques, et en tous cas, toutes les informations sont claires, puisque je donne les matrices d'adjacence en même temps que les graphiques. J'ai l'impression que je devrais justifier le fait que je n'ai pas écarté les graphes par un sommet isolé (et donc, évidemment, un déterminant qui disparaît). Je ne les ai pas écartés car cela rend la réponse plus systématique, reproductible et vérifiable.

enter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description hereenter image description here

Ce qui précède suggère fortement que il n'existe pas de graphe à six sommets dont la valeur du d.a. est de $-2$ ou $2$. Il y a faites existe dix graphes avec une valeur a.d. de $-4$ ou $4$ bien que, à savoir, les graphes no. 63, 65, 109, 110, 113, 116, 121, 126, 127, 149. Nous devons considérer chacun d'eux à tour de rôle et analyser s'il existe des sommets dont la suppression laisse un graphe avec la même valeur de l'a.d.-.

Pour le graphe n° 63, qui a un a.d. de 4$, la suppression de n'importe quel sommet aboutit à un graphe isomorphe au graphe n° 30 (dans la liste des graphes à cinq sommets), qui a un a.d. de $-2neq 4$, donc 63 n'est pas un exemple.

Pour le graphe n° 65, qui a un a.d. de 4$, nous devons distinguer des cas pour analyser les effets des suppressions de sommets.

  • en supprimant le sommet $4$, on obtient un graphe isomorphe au graphe n°34, qui a un a.d. $-4neq 4$.

  • en supprimant le sommet $0$ ou $1$, il en résulte un graphe isomorphe au graphe n°31, qui a un a.d. $-2neq 4$.

  • en supprimant le sommet $2$, on obtient un graphe isomorphe au graphe n°30, qui a un a.d. $-2neq 4$.

  • en supprimant le sommet $3$ ou $5$, on obtient un graphe isomorphe au graphe no. 32 résulte, qui a un a.d. $-2neq 4$.

Comme ce qui précède épuise toutes les suppressions de sommets possibles, et que l'a.d. a toujours changé, le graphe n° 65 n'est pas un exemple.

Pour le graphe n° 109, qui a un a.d. $-4$, la suppression de tout sommet donne un graphe isomorphe au no. 16. qui a un a.d. de $0neq -4$, donc no. 109 n'est pas un exemple.

Pour le graphique n° 110, qui a un a.d. $-4$, il faut à nouveau distinguer les cas : la suppression du sommet $0$ donne un graphe isomorphe au graphe n°22, qui a un a.d. $2neq -4$, tandis que la suppression du sommet $1$ ou $2$ donne le graphe no. 16 avec un a.d. de $0$, et la suppression de $3$ ou $4$ donne le graphe no 31 avec un a.d. de $-2neq -4$, et enfin la suppression du sommet $5$ donne le graphe no 17 avec un a.d. de $0neq -4$ ; cela montre que le graphe no 110 n'est pas non plus un exemple.

Pour le graphe n° 113, qui a un a.d. de $-4$,
en supprimant $0$ on obtient le graphe n°22$ avec un a.d. de $2neq -4$,
tandis que la suppression de $1$ ou $2$ donne le graphe n°23 avec un a.d. $0neq-4$, tandis que la suppression de $3$ ou $4$ donne le graphe n°32 avec un a.d. $-2neq-4$, et enfin la suppression de $5$ donne le graphe n°24. Cela montre que le n° 113 n'est pas un exemple.

Pour le graphique n° 116 Si l'on supprime $0$, $1$ ou $2$, on obtient le n° 26 avec un nombre de points de référence de $-2neq 4$,
tandis qu'en supprimant $3$ ou $4$, on obtient le n° 33 dont l'a.d. est $-2neq 4$, mais en supprimant $5$, on obtient le n° 29 dont l'a.d. est $4=4$.
Donc le n° 116 est un exemple. 116 est un exemple, à savoir l'exemple trouvé par Philipp Lampe. Dans cet exemple, exactement un des sommets possède la propriété requise.

Pour le graphe n° 121, qui a un a.d. de 4$, la suppression du sommet $0$ ou $2$ donne le n° 24 avec un a.d. de $-2$, tandis que la suppression de $1$ donne le n° 34 avec un ad. $-4neq 4$, tandis que la suppression de $3$ donne le n° 31 avec a.d. $-2neq 4$, tandis que la suppression de $4$ donne le n° 33 avec a.d. $-2neq 4$,
et en supprimant $5$, on obtient le n° 26 avec un écart-type de $-2neq 4$. Cela montre que le graphique n° 121 n'est pas un exemple.

Pour le graphique n° 126, dont l'a.d. est $-4$, la suppression de $0$ ou de $4$ donne le n° 23 dont l'a.d. est $0$, tandis que la suppression de $1$ donne le n° 16 dont l'a.d. est $0neq -4$, tandis que la suppression de $2$ ou de $5$ donne le n° 17 dont l'a.d. est $0neq -4$, mais la suppression de $3$ donne le n° 34 dont l'a.d. est $-4=-4$. Par conséquent, le graphique n° 126 est un autre exemple du type requis. C'est l'exemple donné au tout début de cette réponse.

Pour le graphique n° 127, dont l'a.d. est $-4$, la suppression de $0$, $3$ ou $4$ donne le n° 24 dont l'a.d. est $-2neq-4$, tandis que la suppression de $1$, $2$ ou $5$ donne le n° 17 dont l'a.d. est $0neq -4$.
Cela épuise tous les sommets et montre que le n° 17 n'est pas un exemple.

Pour le graphe n°149, qui a un a.d. de 4$,
et en supprimant $0$ ou $5$ on obtient le n° 26 avec un a.d. de $-2neq4$,
tandis que la suppression de $1$, $2$, $3$ ou $4$
donne le n° 32 dont l'a.d. est $-2neq 4$.
Cela montre que le n° 149 n'est pas un exemple.

Nous avons maintenant considéré tous les candidats,
et trouvé exactement deux exemples du genre
demandés par l'OP, à savoir, les deux graphes
donnés dans la proposition au début de
cette réponse. Ceci prouve la proposition.

Remarques finales.

  • Le rapport assez faible de $frac{2}{156} = frac{1}{78}$ suggère la question de savoir si la limite.

$lim_{ntoinfty}frac{text{nombre de graphes non étiquetés sur $n$ avec au moins un sommet du genre requis}{text{nombre de tous les graphes non étiquetés sur $n$}}$.

existe et ce qu'il est. Tout ce qui n'est pas le fait qu'il soit $0$ me semblerait surprenant, mais je ne sais pas comment le prouver.

  • De manière embarrassante, je ne connais pas de construction qui répondrait à la question évidente de.

si pour chaque $ngeq 6$ il existe au moins un graphe sur $n$ ayant la propriété requise (c'est-à-dire un déterminant non nul de la matrice d'adjacence, et il existe au moins un sommet dont la suppression laisse un graphe avec le même déterminant de matrice d'adjacence).

  • Noam Elkies à 2018-03-05 17:23:37Z a souligné l'ambiguïté intéressante dans la formulation verbale de la question de l'OP, qui ne permet pas de savoir quel est le quantificateur logique prévu régissant le sommet supprimé. Les deux interprétations sont possibles. Bien que l'acceptation de la réponse par le PO à 2018-03-05 18:38:11Z semble suggérer que le PO voulait dire un quantificateur existentiel, l'autre interprétation est intéressante et une question ouverte ; c'est-à-dire,

Problème ouvert. Existe-t-il un graphe fini tel que le déterminant de sa matrice d'adjacence soit non nul et en supprimant. tout de ses sommets aboutit à un graphe dont la matrice d'adjacence a la même valeur que précédemment ?

Mise à jour du 13 mars 2018 . Je suis maintenant enclin à penser que, contrairement à mes attentes initiales, un graphe du type ci-dessus est impossible : En deux heures désœuvrées, j'ai vérifié expérimentalement presque.tous les les graphes nommés à

http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html

et dans le cas du constructeur de graphe permettant des paramètres, j'ai expérimenté de nombreuses valeurs de ces paramètres. De plus, j'ai testé plusieurs milliers de graphes circulants (à ce jour, à peu près $10^6$ circulants non isomorphes, sur entre 11 et 100 sommets, grosso modo), et pour de nombreuses tailles d''ensembles de connexions', chaque 'ensemble de connexions' étant choisi aléatoirement. J'ai également testé des graphes aléatoires (bien que là, on sait dès le départ qu'il n'y a aucune chance, car les a.d. des sommets supprimés n'auront clairement pas tous la même valeur). Les résultats ont été les suivants :

Il y a plus d'exemples que je n'ai envie de décrire de l'a.d. étant non nul alors que l'a.d. après la suppression de sommet diffère de l'a.d. précédent par $1$ seulement. Cependant, étonnamment, on n'a pas trouvé un seul exemple du type requis par l'OP. parmi des milliers de graphes non isomorphes. Cela m'a surpris, car c'était contraire à ce que j'avais prévu. D'après mes expériences avec des circulants de petite taille (qui se rapprochaient de ce que le PO et Noam Elkies demandaient), je m'attendais à ce que l'exploration aléatoire de circulants légèrement plus grands permette de trouver rapidement un exemple. Ce n'était pas le cas, et je suis passé à des circulants sur une centaine de sommets, et à des ensembles d'intersection de taille d'environ $5$ (résultant en des graphes réguliers de $10$).

Je suis bien conscient que les circulants sont des graphes très spéciaux et que généraliser à partir d'eux à tous les graphes est plutôt injustifié. A ce jour, je serais cependant très surpris qu'il existe une réponse affirmative à la question du problème ouvert qui.était un circulant. Il semble qu'il y ait un principe à l'œuvre qui empêche la différence

$det(mathrm{A}(G))-det(mathrm{A}(G)|_{(nsetminus{i})times(nsetminus{i})})$

ce qui pour un circulant ne dépend bien sûr pas de $i en n$, jusqu'à $0$, sauf dans le cas trivial où les déterminants sont tous deux $0$. Pour me répéter , cette différence peut facilement être ramenée à $1$ ou $-1$. (j'ai vu des centaines d'exemples), bien que je ne sache toujours pas comment caractériser les circulants réalisant cela.

Il pourrait y avoir une vérité mathématique appréciable derrière ces résultats expérimentaux. Il y a peut-être même une compréhensible raison. Je trouve en particulier intriguant que l'on puisse arriver à 1$ près de ce qui est demandé, ce qui est aussi proche que possible, sauf pour une solution pure et simple.

Donc, à moins que vous ne chérissiez le processus lui-même, ne cherchez pas dans http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html pour un exemple, car je prédis que vous n'en trouverez pas. (Il s'agit d'un jugement intuitif approximatif de la probabilité, " bayésien " en quelque sorte, et non d'une déclaration fréquentiste exacte). A mon avis personnel, il semble plus judicieux d'essayer de prouver la conjecture selon laquelle un tel graphe est impossible.

Mise à jour du 14 mars 2018 . Je pense qu'il n'est pas improbable que quelqu'un (comme moi) trouve l'article.

[BLP2014] Bapat, R.B. ; Lal, A.K. ; Pati, S. Une formule pour tous les mineurs de la matrice d'adjacence et une application. Spec. Matrices 2, n° 1, 89-98 (2014).

et (comme moi) pense initialement que cela pourrait aider avec le problème ouvert. Je ne trouve rien à redire à cet article intéressant, mais je pense que cela pourrait faire gagner du temps à quelqu'un d'autre de souligner que contrairement à ce que le titre pourrait suggérer, l'article [BLP2014] peut être complètement ignoré en ce qui concerne le problème ouvert.; la raison en est que l'objectif principal de [BLP2014] sont les mineurs qui sont indexés par de tels ensembles tels que l'ensemble indexant les "lignes" du mineur est disjoint de l'ensemble indexant les "colonnes" du mineur. alors que le problème du PO concerne des mineurs indexés par des ensembles de la forme $(nsetminus{i})times(nsetminus{i})$ avec $iin n$, ce qui est à peu près aussi éloigné de l'objet principal de la norme [BLP2014] que possible. Je ne dis pas que [BLP2014] avait un titre trompeur : en effet, tout type de mineur est pris en charge, mais pour les mineurs du type pertinent pour le présent problème ouvert, la formule de l'article [BLP2014] revient précisément à la formule dans [H1962, page 208] (pour s'en rendre compte, il faut lire jusqu'à la remarque 3.2 de l'article [BLP2014]).

Références.

[A2012] Alireza Abdollahi, Déterminants des matrices d'adjacence des graphes., Transactions on Combinatorics, vol. 1, n° 4 (2012), p. 9-16.

[B1993] Norman Biggs, Théorie algébrique des graphes, Cambridge University Press, 1993, ISBN 9780521458979

[BLP2014] Bapat, R.B. ; Lal, A.K. ; Pati, S. Une formule pour tous les mineurs de la matrice d'adjacence et une application. Spec. Matrices 2, n° 1, 89-98 (2014).

[H1962] Frank Harary, Le déterminant de la matrice d'adjacence d'un graphe., SIAM Review, vol. 4, n° 3, (1962), p. 202-210.

Notes de bas de page.

(*) Accessoirement, le cas $n=10$ semble être à la portée des machines contemporaines, même avec le code de haut niveau non optimisé que j'ai donné ci-dessus. Pourtant, il est à la portée des machines dont je dispose. Si certains lecteurs ont accès à une machine puissante ou à un cluster, et ont installé Sage, alors l'exécution du code que j'ai donné avec

'graphs(9)' remplacé par 'graphs(10)',

et

'range(274668)' remplacé par 'range(12005168)' (qui est le nombre de classes d'isomorphisme de graphes sur 10 sommets).

donnera probablement les valeurs de l'a.d. pour $n=10$ en un temps et une mémoire raisonnables.

J'apprécierais que l'on m'envoie le résultat de 'histo' pour $n=10$ (par exemple sous forme de commentaire), et je l'ajouterais ensuite à ce fil de discussion. Le cas $n=11$ est, je suppose, hors de portée sans louer une quantité non négligeable de temps et de mémoire sur un supercalculateur.

(**) Il convient de souligner que la distribution des valeurs de l'a.d. est de pas symétrique autour de $0$.
Cela peut paraître surprenant à première vue, mais le devient moins si l'on réalise que les opérations habituelles qui permutent le signe d'un déterminant, et qui peuvent souvent être utilisées pour prouver la symétrie des valeurs espérées évanouissantes, sont les suivantes . pas disponibles ici : permuter deux lignes (ou colonnes) fait pas résulte en une autre matrice d'adjacence d'un graphe.

N'oubliez pas que vous avez le privilège de commenter.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.