BWL-Lexikon.de
  • Home
  • Grundlagen
    • Aufbau eines Betriebs
    • Definitionen
    • Organisation
    • Personalwirtschaft
    • Planung und Entscheidung
    • Produktionsfaktoren
    • Unternehmensführung
  • BWL
    • Rechtsformen
    • Rechnungswesen
      • Finanzbuchhaltung
      • Kostenarten
      • Jahresabschluss
    • Marketing
    • Logistik
      • Logistik Kennzahlen
      • Beschaffung
      • Lagerverfahren
      • Materialarten
    • Kennzahlen
      • Bilanzkennzahlen
      • Produktivitätskennzahlen
      • Rentabilitätskennzahlen
      • Kennzahlen der GuV
  • VWL
    • Makroökonomie
    • Mikroökonomie
  • Fehler gefunden?

Du bist hier: Startseite » Alle Lektionen » Aufbau eines Betriebs » Planung und Entscheidung » Operations Research » Bipartiter Graph

Bipartiter Graph

Enthält: Beispiele · Definition · Formeln · Grafiken · Übungsfragen

Ein Graph wird dann als bipartit bezeichnet, wenn die enthaltenen Knoten in zwei Teilmengen aufteilbar sind, deren Knoten untereinander keine verbindenden Kanten aufweisen.

Du lernst in diesem Abschnitt was man unter bipartiten Graphen versteht, warum sie wichtig sind und welche weiteren Typen von Graphen es gibt.

Synonym: paarer Graph

Inhalt dieser Lektion

  • Warum sind bipartite Graphen wichtig?
  • Was versteht man unter bipartiten Graphen?
  • Was versteht man unter bipartiten Graphen?
    • Eigenschaften bipartiter Graphen
  • Weitere Typen von Graphen
    • Sterngraphen
    • Vollständige Graphen
    • Digraphen
  • Übungsfragen

Warum sind bipartite Graphen wichtig?

Mit Hilfe von bipartiten Graphen lassen sich die Beziehungen der Elemente zweier Teilmengen A und B zueinander beschreiben. Mit Hilfe bipartiter Graphen können vor allem Zuordnungsprobleme bestens untersucht werden. Außerdem ist die Berechnung vieler Eigenschaften bei bipartiten Graphen mit einem geringeren Aufwand verbunden.

Was versteht man unter bipartiten Graphen?

Bipartite Graphen haben die Eigenschaft, dass sich ihre Knoten in zwei disjunkte Teilmengen (A und B) unterteilen lassen. Das bedeutet, dass unter den Knoten einer jeweiligen Teilmenge keine Kanten existieren, die die Knoten innerhalb einer Teilmenge miteinander verbinden.

Was versteht man unter bipartiten Graphen?

Bipartite Graphen haben die Eigenschaft, dass sich ihre Knoten in zwei disjunkte Teilmengen (A und B) unterteilen lassen. Das bedeutet, dass unter den Knoten einer jeweiligen Teilmenge keine Kanten existieren, die die Knoten innerhalb einer Teilmenge miteinander verbinden.

Bipartiter Graph: Disjunkte Teilmengen
Bipartiter Graph: Disjunkte Teilmengen

Die Teilmengen A und B der Elemente des Graphen heißen Partitionsklassen. Die Menge {A,B} wird als Bipartition des Graphen G bezeichnet.

Ist die Anzahl der Kanten im Graphen maximal, ist also jeder Knoten aus der Teilmenge A mit jedem Knoten B verbunden, so spricht man von einem vollständig bipartitem Graph. Dieser wird mit Kn,m bezeichnet. m und n bezeichnen dabei die jeweilige Anzahl der Knoten aus den Mengen A und B.

Vollständig bipartiter Graph
Vollständig bipartiter Graph

Eigenschaften bipartiter Graphen

Einen bipartiten Graph erkennt man anhand folgender Eigenschaften:

  • Bei den Teilmengen A und B handelt es sich um stabile Mengen. Sie sind nicht adjazent zueinander.
  • Bipartite Graphen haben ein maximales bzw. perfektes Matching.
  • 2-färbbare Graphen sind bipartit, d.h. den jeweiligen Partitionsklassen können eindeutige Farben zugewiesen werden.
  • Die Knotenüberdeckungszahl bipartiter Graphen ist gleich der Paarungszahl.

Weitere Typen von Graphen

Neben den bipartiten Graphen gibt es auch noch andere Typbezeichnungen für Graphen, die sich nach den jeweiligen Eigenschaften richten.

Hierzu gehören:

  • Sterngraphen
  • Vollständige Graphen
  • Digraphen

Sterngraphen

Als Sterngraph bezeichnet man einen Graphen, wenn eine der Teilmengen gleich 1 ist. Sterngraphen, die über n Kanten verfügen werden mit Sn oder auch K1,n bezeichnet.

Ein Sterngraph mit der Bezeichnung K1,4 könnte also folgendermaßen aussehen:

Sterngraph
Sterngraph

Vollständige Graphen

Vollständige Graphen haben die Eigenschaft, dass jeder Knoten n mit jedem anderen Knoten durch eine Kante verbunden ist.

Die Anzahl der Kanten in einem vollständigen Graph kann mit Hilfe der Dreieckszahl berechnet werden:

    \[ \Delta_{n-1} = \frac{n*(n-1)}{2} \]

Beispiel
Der Graph G enthält fünf Knoten, die alle miteinander verbunden sind.

Eingesetzt in die Formel bedeutet das:

    \[ \Delta_{5-1} = \frac{5*(5-1)}{2} = 10 \]

In unserem vollständigen Graph K5 existieren also 10 Kanten.

Vollständiger Graph
Vollständiger Graph

Digraphen

Ein einfacher gerichteter Graph mit einer endlichen Menge an Knoten wird als Digraph bezeichnet. Er zeichnet sich dadurch aus, dass keine parallelen Pfeile und keine Schlingen existieren.

Digraphen
Digraphen

Übungsfragen

#1. Was versteht man unter einem bipartiten Graphen?

#2. Was versteht man unter einem Sterngraphen?

#3. “Die Teilmengen A und B der Elemente des Graphen heißen Partitionsklassen.” - diese Aussage ist:

#4. “Bei den Teilmengen A und B eines bipartiten Graphen handelt es sich um instabile Mengen. ” - Diese Aussage ist:

#5. “Bei einem vollständig bipartitem Graph ist jeder Knoten der Teilmenge A mit jedem Knoten der Teilmenge B verbunden. Die Anzahl der Kanten ist damit maximal.” - diese Aussage ist:

Fertig

Ergebnis

Könnte dich auch interessieren:

Inzidenzmatrix bei ungerichteten Graphen

Inzidenzmatrix

In der Inzidenzmatrix werden die Beziehungen der Knoten und der Kanten eines Graphen abgebildet. In diesem Kapitel zeigen wir dir, … weiterlesen >>

Graphentheorie

Graphentheorie

Die Graphentheorie als mathematische Methode befasst sich mit der Untersuchung von Graphen als Darstellung von einer Vielzahl von Problemen. Insbesondere … weiterlesen >>

Kruskal Algorithmus - Anwendungsbeispiel: Gegebener Graph

Kruskal Algorithmus

Der Kruskal Algorithmus dient der Ermittlung des minimalen Spannbaums eines zusammenhängenden und gewichteten Graphen. Wir zeigen dir in diesem Kapitel, … weiterlesen >>

Adjazenzmatrix bei gewichteten Graphen

Adjazenzmatrix

Die Adjazenzmatrix ist eine Matrix, die die Anzahl der Knoten in einem Graphen und deren Beziehungen zueinander darstellt. Damit lässt … weiterlesen >>

Prim Algorithmus - Anwendungsbeispiel: Finaler Graph

Prim Algorithmus

Der Prim Algorithmus wird genutzt, um den minimalen Spannbaum eines Graphen zu finden. Er kann in Graphen genutzt werden, die … weiterlesen >>

Nichts passendes dabei?

Erkunde andere Fachbereiche oder benutze die Suchfunktion. Falls Du keine Antwort auf Deine Frage findest, schick uns gerne eine Nachricht, wir versuchen dann passenden Content für Dich zu schaffen.

Zur Übersicht
Oder lieber die Suche benutzen?
  • Eselsbrücke
  • |
  • Buchungssatz
  • |
  • Formeln
  • |
  • Beispiele
  • |
  • Grafiken
  • |
  • Definition
  • |
  • Übungsfragen
  • © BWL-Lexikon.de
  • Datenschutz
  • Impressum
  • Cookie Einstellungen
Fehler gefunden?

Danke, dass du dir die Zeit nimmst, uns dein Feedback zu geben. Bitte beschreibe so genau wie möglich wo du einen Fehler gefunden hast.