Mathématiques pour la gestion ! (graphes)

[Jib]

Bonjour à tous,

Voilà, j'ai une petite question. Mon prof de maths aime bien nous donner des exercices où on ne comprend pas ce qu'il faut faire ! lol
Voici donc l'énoncé en :


Pour la réponse a) je crois avoir une idée :
- théorème des poignées de mains :"la somme des degrés de tous les sommets est égale à 2 fois le nombre d'arrêtes".
Dans ces cas là, la première suite n'est pas possible car la somme des degrés des sommets est égale à 17 et cela donnerai 8,5 arretes => impossible.
En revanche, la deuxième suite me semble possible car on a 18, ce qui donnerai 9 arrètes.

Qu'en pensez vous?

En revanche, pour la suite de l'exercice, je suis vraiment dans le flou !^^

Avez vous une idée ?

Merci.
Jibé

[Flodelarab]

Cet exercice me gêne. Est il sous-entendu qu'entre 2 sommets il y a un maximum de 1 arrête ? Si oui, alors la seconde n'est évidemment pas graphique. Sinon, l'énoncé est gênant car il n'y a nulle part un exemple de graphe dont la somme des degrés serait pair et qui ne serait pas graphique.

[busard_des_roseaux]

Voilà, j'ai une petite question. Mon prof de maths aime bien nous donner des exercices où on ne comprend pas ce qu'il faut faire !

bonjour,

Dans le cas présent , l'exercice est (très) intéressant.

L'idée est d'associer à un graphe non orienté une suite d'entiers.
On se demande si toute suite provient d'un graphe (surjectivité). A la question (2), on réduit une suite quelconque à une suite plus simple par un algorithme qui conserve le graphisme éventuel.
Et ainsi, une fois l'algorithme effectué sur une suite donnée, on peut conclure si elle provient d'un graphe ou non.

n'hésite pas à tester sur de nombreux graphes et sur de nombreuses suites les propriétés à démontrer ou au contraire à infirmer. Il est si simple de construire des exemples. Tu peux aussi récurrer sur le nombre de sommets ou le nombre d'arêtes en commençant par des graphes très simples et augmenter progressivement le nombre de sommets ou d'arêtes. regarder ce qui se passe avec plusieurs composantes connexes. Bref, expérimenter.

[busard_des_roseaux]

Est il sous-entendu qu'entre 2 sommets il y a un maximum de 1 arrête ?

oui, je viens de regarder sur google. C'est la déf. d'un graphe simple.
------------------------------------
(5,5,4,4,0). Il y a un sommet d'indice 5. La suite devrait être de longueur 6. Non graphique.
------------------------------------
On applique l'algorithme:
(6,5,5,4,3,3,2,2,2)
(4,4,3,2,2,1,2,2)=(4,4,3,2,2,2,2,1)
(3,2,1,1,2,2,1)=(3,2,2,2,1,1,1)
(1,1,1,1,1,1)
Cette dernière suite provient de trois segments de droites non connectés.
Graphique.
----------------------------------------
On peut supprimer les zéros en fin de liste. Ils correspondent à des sommets isolés.
(6,6,6,6,4,3,3)
après réductions successives, on obtient (3,1) qui n'est pas graphique, trop de connexions et pas assez de sommets.
--------------------------------------------------------
c) En partant d'une suite numérique de la forme (2), supposée graphique, on ajoute un nouveau sommet qu'on connecte aux s premiers sommets de

[Flodelarab]

oui, je viens de regarder sur google. C'est la déf. d'un graphe simple.

Certes. Mais justement, un graphe peut être orienté ou non , indépendamment de sa simplicité ou non. L'énoncé ne parle nulle part d'une possible simplicité.

[bruce.ml]

Le résultat à admettre de la question b) est faux ... Et l'énoncé en donne gentiment un contre exemple.

[Flodelarab]

Le résultat à admettre de la question b) est faux ... Et l'énoncé en donne gentiment un contre exemple.

:hein:
Peux tu être plus précis ?
L'énoncé est repris en exemple dans le b) et semble marcher

[bruce.ml]

:hein:
Peux tu être plus précis ?
L'énoncé est repris en exemple dans le b) et semble marcher

on obtient une suite non décroissante, donc non graphique. Alors je suis d'accord que c'est juste si on se place dans ~ où ~ est la relation d'équivalence a~b ssi il y a une permutation entre a et b. Ou en termes moins pompeux, si on trie : mais ce n'est dit nulle part !

[busard_des_roseaux]

bien sûr, l'hypothèse de la question (2) est fausse.
Mais l'énoncé précise: admettons la provisoirement.