Ein ungerichtetes Diagramm wird gegeben, und zuerst muss ich die geringste Anzahl von Kanten finden, um es ungeraden Zyklus zu haben und zweitens sollte ich die Möglichkeiten finden, hinzuzufügen diese KantenMöglichkeiten zum Hinzufügen der kleinsten Kante zu einem Graphen, um es Oddcycle-Diagramm
Färbung des Graphen schwarz und weiß mit, das heißt, aus beliebigen Ausgangspunkt schwarz verwenden, das Streichen der benachbarten, nicht gemalt Knoten mit weißen und Werke auf diesen weißen Knoten ähnlich.
Überprüfen Sie, ob eine Kante Knoten mit derselben Farbe hat. Wenn ja, gibt es bereits einen ungeraden Zyklus.
Andernfalls führt die Verbindung von zwei Knoten mit derselben Farbe zu einem ungeraden Zyklus. Das heißt, Sie benötigen genau eine zusätzliche Kante, und Sie haben C (number_of_black_nodes, 2) + C (number_of_white_nodes, 2) Möglichkeiten, dies zu tun.
Hinweis: Sie können immer 3 Kanten hinzufügen, um ein Dreieck zu erstellen. –
@j_random_hacker Ja, aber manchmal werden keine zusätzlichen Kanten benötigt :) – behnam
Der Hinweis soll Sie darüber nachdenken, wie Sie diese Fälle angehen. –