Répondre à la discussion
Affichage des résultats 1 à 4 sur 4

Théorie des graphes: un seul chemin



  1. #1
    Brumaire

    Théorie des graphes: un seul chemin


    ------

    Bonjour,

    J'ai trouvé les propriétés suivantes :
    Soit G= (E, K) un graphe,
    - si chacun des deux noeuds de G peuvent être reliés par une arrête, alors G est, deux noeuds du graph sont toujours reliables par une chaîne.

    - Si G n'a pas de boucle,
    alors G ne peut être un arbre, que si, pour tous les noeuds, deux noeuds différents peuvent être reliés par une unique chaîne.

    Je n'ai aucune idée pour la démonstration de la première propriété. Je voudrais donc quelques conseils.

    Pour la deuxième, je pense qu'il faut dire qu'un arbre ne peut pas accepter de cycles. Donc s'il y avait deux chaines, ce ne pourrait être un arbre.
    Qqun pourrait-il m'aider à rendre cette démonstration plus cohérente?

    Merci d'avance

    -----

  2. #2
    martini_bird

    Re : Théorie des graphes: un seul chemin

    Salut,
    Citation Envoyé par Brumaire
    Bonjour,
    J'ai trouvé les propriétés suivantes :
    Soit G= (E, K) un graphe,
    - si chacun des deux noeuds de G peuvent être reliés par une arrête, alors G est [???], deux noeuds du graph sont toujours reliables par une chaîne.
    je cherche le mot manquant: connexe?

  3. #3
    BS

    Re : Théorie des graphes: un seul chemin

    Salut,

    Je ne comprends pas très bien ton énoncé. Est-ce
    si G est connexe, alors deux noeuds sont toujours reliables par un chaîne ? La connexité étant alors entendue au sens topologique ?

    Citation Envoyé par Brumaire
    - si chacun des deux noeuds de G peuvent être reliés par une arrête, alors G est, deux noeuds du graph sont toujours reliables par une chaîne.

  4. #4
    Brumaire

    Re : Théorie des graphes: un seul chemin

    Oui mais comment démontrer la connexité peut se généraliser ?? Je me demande maintenant s'il ne faut pas faire un raisonnement par récurrence.
    Pour la deuxième propriété, je trouve ma démonstration un peu légère même si le principe doit être là.

Discussions similaires

  1. Théorie des graphes
    Par -Zweig- dans le forum Lectures scientifiques
    Réponses: 4
    Dernier message: 21/12/2007, 11h05
  2. Theorie des graphes
    Par BioBen dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 29/11/2007, 18h25
  3. BOINC et théorie des graphes : une nouvelle performance !
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 1
    Dernier message: 14/02/2007, 13h51
  4. Théorie des graphes et graphes de liaisons
    Par Eogan dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/12/2006, 22h59