algorithme de découverte de graphes si le graphe est connecté, bipartite, a un cycle et est un arbre

Je suis venu pour un problème quand j'ai essayé de travailler avec des graphiques et écrire un peu de code pour elle, mais avec pas de chance :/!!

J'ai voulu créer quelque chose qui va prendre les données du graphique et vérifier si elle est:
1 - relié
2 - bipartite
3 - a cycle
4 - est un arbre

donc je me demandais par exemple si cela peut être écrit à lire un graphique les données d'un .txt fichier qui vous permettra de faire les tests ci-dessus ??

à l'aide de simples bord-format de liste est la bonne approche ?

votre aide est très appréciée si vous pouvez me donner un lien pour lire sur la façon d'effectuer cette tâche ou d'un coup de pouce pour un code !!

merci 😀

source d'informationauteur Moe

  1. 25

    vérifier si il est:

    1. connecté

    Pour celui-ci, vous essayez de parcourir l'ensemble du graphique à partir d'un point et de voir si vous réussissez. À la fois la profondeur de la première traversée et en largeur d'abord la traversée sont acceptables ici. Cet algorithme va diviser le nœud dans les composants:

    • marque de tous les nœuds que non visités
    • pour chaque nœud csi ce nœud est non visités
      • créer un nouveau vide ensemble de nœuds, le composant en cours
      • enqueue ce nœud pour la traversée de
      • bien qu'il y est un nœud t de file d'attente
        • supprimer ce nœud à partir de la file d'attente
        • marquer tous les non visités voisin que d'ouvrir et de mettre en file d'attente pour la traversée de
        • marque de ce nœud traversée
        • ajouter ce nœud pour le composant en cours
      • fermez le composant en cours, et l'ajouter à l'ensemble de composants

    Si il y a un seul composant, le graphique est connecté.

    Si une file d'attente est utilisée, l'algorithme est d'une ampleur-première recherche. Si une pile est utilisée, l'algorithme est en profondeur d'abord de recherche. Toute autre collection avec le push et pop-toutes les opérations à faire. D'intérêt particulier est la pile des appels: remplacer "mettre en file d'attente pour la traversée" avec "parcourir récursivement"

    Pour les graphes orientés, il y a deux concepts liés: Un graphe orienté est faiblement connecté ssi il est connecté en négligeant tous les bords directions. Un graphe orienté est fortement connexe ssi chaque nœud est accessible à partir de chaque nœud. Pour tester la forte connexité il sufficces de vérifier chaque nœud est accessible à partir du premier nœud en utilisant uniquement de l'avant bords, et chaque noeud est accessible à partir du premier noeud en utilisant uniquement vers l'arrière bords (le premier nœud est accessible à partir de chaque nœud).

    1. bipartite

    Un graphe est biparti ssi il est bicolorable. Essayez d'attribuer une bicoloring, et si vous échouez, le graphique n'est pas bipartite. Ce peut être incorporé dans l'algorithme précédent: Chaque fois que vous marquez un noeud ouvert, lui attribuer une couleur, à l'opposé de la couleur attribuée à son voisin t. Quand un voisin de t est déjà ouvert, vérifier la couleur. Si sa couleur est la même que celle de til n'y a pas de bicoloring.

    1. de cycle

    C'est facile: Si vous observez tout nœud qui est déjà ouvert, il y a un cycle. Notez que tout graphe qui n'a pas de cycle est biparti.

    Dans les graphes orientés, cela permettra de détecter la présence d'un non-orienté cycle. Pour détecter la présence d'dirigé cycles, utilisez la commande suivante (tri topologique) algorithme:

    • bien qu'il y est un nœud avec le indegree de zéro
      • ajouter le nœud pour le tri topologique (non pertinent pour la détection de cycles)
      • supprimer le nœud du graphe
    • si il y a toujours un nœud dans le graphe
      • le graphe contient un tel cycle. Pas de tri topologique sur ce graphique
    • d'autre
      • le graphe ne contient pas un tel cycle est acyclique). Le tri topologique généré est valide.
    1. arbre

    Un graphe non-dirigé est un arbre ssi il est connecté, et ne contient aucun cycle.

    Un graphe orienté est un enracinée arbre ssi il n'a pas non orienté cycles et il y a un seul sommet avec un indegree de zéro (une seule racine). Aussi, un graphe orienté est un enracinée arbre ssi il est connecté, n'a pas non orienté, et les cycles de chaque nœud avec un outdegree de zéro a une indegree d'au plus un (tout évier est une feuille).