Diese Arbeit befasst sich hauptsächlich mit der Partitionierung und dem Zusammenhang von Graphen. Als erstes zeigen wir, dass das Problem, die Knoten eines Graphen in eine vorgegebene Anzahl an Teilmengen zu teilen, sodass die induzierten Subgraphen jeweils isomorph zueinander sind, NP-vollständig ist. Wenn die induzierten Subgraphen auch noch zusammenhängend sein sollen, bleibt das Problem NP-vollständig. Anschließend untersuchen wir spezielle Graphenklassen für die dieses Problem in Polynomialzeit gelöst werden kann. Danach betrachten wir das Polytop, welches durch die Inzidenzvektoren von Knoten induziert wird, welche einen zusammenhängenden Subgraphen induzieren. Wir untersuchen facettendefinierende Ungleichungen und deren allgemeine Struktur. Für spezielle Graphenklassen geben wir eine vollständige Beschreibung an. Danach befassen wir uns mit dem Problem, die Knoten eines Graphen so in eine gegebene Anzahl an Teilmengen zu partitionieren, dass die induzierten Subgraphen zusammenhängend sind. Für das entsprechende Polytop zeigen wir die Dimension und facettendefinierende Ungleichungen. Diese theoretische Betrachtung wird durch das Problem erweitert, die Knoten eines Graphen in eine vorgegebene Anzahl zu partitionieren, sodass die induzierten Graphen zusammenhängend sind, derart, dass der entsprechende Schnitt maximiert wird. Wir stellen verschiedene Wege vor, dieses Problem in SCIP zu lösen und zeigen numerische Resultate. Hierdurch werden interessante Problem für MIPs im generellen angedeutet. Da dieses Problem in der Literatur im Allgemeinen nur durch die zulässige Menge definiert wird, betrachten wir die Zielfunktion. Hierfür betrachten wir das Problem, MIPs für Probleme mit nicht-linearer Zielfunktion zu finden. Wir diskutieren Eigenschaften und Voraussetzungen für die Existenz oder Nichtexistenz spezieller Formulierungen. Als letztes betrachten wir das Problem, die Knoten eines Graphen so zu partitionieren, dass alle bis auf einen induzierten Graphen isomorph sind. Dieses Problem wird interessant, wenn die Menge, die nicht die Isomorphie induziert, minimiert wird. Hierfür stellen wir auch eine Technik vor, die auf Brute-Force basiert. Statt den Graphen in isomorphe Teile zu zerlegen, untersuchen wir noch ähnliche Graphen. In diesem Fall betrachten wir verschiedene Definitionen von Ähnlichkeit und stellen vor, wie diese implementiert worden sind.