📚 الرئيسية
دخول

مسابقة دكتوراه 2013 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 03

مسابقة تخصص · Algèbre · المدة: 2سا

⬇️ تحميل☆ حفظ✓ تم الحل

Concours d’accès à la Formation Doctorale Recherche Opérationnelle et Mathématiques Discrètes, ROMaD, épreuve de Mathématiques Discrètes, USTHB, Faculté de Mathématiques, 20 octobre 2013, durée 2h.

التمرين 1

Exercice 1 — Coloration des graphes planaires

#graph-coloring#planar-graphs#perfect-graphs

Soit G=(V,E)G=(V,E) un graphe connexe non orienté.

  1. Montrer que χ(G)≥ω(G)\chi(G)\ge\omega(G).
  2. Montrer que χ(G)α(G)≥∣V(G)∣\chi(G)\alpha(G)\ge|V(G)|.
  3. Montrer que, si GG est planaire, alors χ(G)≤5\chi(G)\le5.
  4. Montrer que, si GG est planaire et parfait, alors χ(G)≤4\chi(G)\le4.
  5. Tout graphe planaire vérifie-t-il χ(G)≤4\chi(G)\le4 ? Justifier.
  6. Proposer un algorithme polynomial de 55-coloration.
◀الحل

1.

Une clique exige des couleurs distinctes.

χ(G)≥ω(G)\boxed{\chi(G)\ge\omega(G)}

2.

Chaque classe de couleur contient au plus α(G)\alpha(G) sommets.

∣V(G)∣≤χ(G)α(G)\boxed{|V(G)|\le\chi(G)\alpha(G)}

3.

Le théorème des cinq couleurs donne χ(G)≤5\chi(G)\le5.

4.

Si GG est parfait et planaire, χ(G)=ω(G)≤4\chi(G)=\omega(G)\le4.

5.

Le théorème des quatre couleurs donne

χ(G)≤4.\boxed{\chi(G)\le4}.

التمرين 2

Exercice 2 — Reconnaissance de classes de graphes

#graph-recognition#bipartite-graphs#perfect-graphs
  1. Déterminer si les graphes multipartis complets sont reconnaissables en temps polynomial et donner un algorithme.
  2. Déterminer si les graphes bipartis sont reconnaissables en temps polynomial et donner un algorithme.
  3. Discuter la complexité du nombre chromatique et du nombre de stabilité dans les graphes parfaits.
◀الحل

1.

GG est multipartite complet si et seulement si G‾\overline G est une union de cliques.

2.

Un BFS à deux couleurs reconnaît un graphe biparti en O(n+m)O(n+m).

3.

χ(G) et α(G) sont calculables en temps polynomial sur les graphes parfaits.\boxed{\chi(G)\text{ et }\alpha(G)\text{ sont calculables en temps polynomial sur les graphes parfaits.}}

التمرين 3

Exercice 3 — Identités du triangle de Pascal

#combinatorics#pascal-triangle#recurrence-relations

Une suite est définie par

Un+1=∑k(n−qkp+rk) ⋆ xkyp+rk.U_{n+1}=\sum_k\binom{n-qk}{p+rk}\,\star\,x^k y^{p+rk}.
  1. Expliquer le rôle de nn, qq, pp et rr, puis remplacer ⋆\star par l’expression correcte.
  2. Montrer que
Un−x(q1)Un−1+⋯+(−1)qxq(qq)Un−q=yqUn−p−q.U_n-x\binom q1U_{n-1}+\cdots+(-1)^qx^q\binom qqU_{n-q}=y^qU_{n-p-q}.
◀الحل

1.

Les paramètres décrivent la ligne, le pas horizontal, le décalage initial et le pas d’indice.

2.

On utilise

∑s=0q(−1)s(qs)(u−sv)=(u−qv−q).\sum_{s=0}^{q}(-1)^s\binom qs\binom{u-s}{v}=\binom{u-q}{v-q}. Un−∑j=1q(−1)j−1xj(qj)Un−j=yqUn−p−q\boxed{U_n-\sum_{j=1}^{q}(-1)^{j-1}x^j\binom qjU_{n-j}=y^qU_{n-p-q}}

التمرين 4

Exercice 4 — Coefficients multinomiaux et hyperdéterminants

#multinomial-coefficients#hypermatrices#determinants
  1. Interpréter combinatoirement le coefficient multinomial et établir la formule de Pascal généralisée.
  2. Pour M=(aijk)1≤i,j,k≤3M=(a_{ijk})_{1\le i,j,k\le3} : a. calculer l’hyperdéterminant lorsque
aijk=(i+j+ki,j,k);a_{ijk}=\binom{i+j+k}{i,j,k};

b. le calculer lorsque aijk=i−j+ka_{ijk}=i-j+k ; c. expliquer la différence fondamentale.

◀الحل

1.

(nn1,…,nr)=∑i:ni>0(n−1n1,…,ni−1,…,nr)\boxed{\binom n{n_1,\ldots,n_r}=\sum_{i:n_i\gt0}\binom{n-1}{n_1,\ldots,n_i-1,\ldots,n_r}}

2.

Le tenseur affine est dégénéré.

Det⁡(i−j+k)=0\boxed{\operatorname{Det}(i-j+k)=0}
→السابقمسابقة الدكتوراه 2013 — Université Badji Mokhtar - AnnabaالتاليConcours Doctorat 2013 — Université Yahia Farès - Médéa — Épreuve N°03←