Bipartiter Graph K: Berechne den Grad jeder Ecke. Wie viele Kanten hat K insgesamt?

Question

Text erkannt:

Aufgabe \( 3 . \) Es seien \( n, m \geq 1 \) zwei ganze Zahlen. Der vollständige bipartite Graph \( K_{n, m} \) ist gegeben durch:
\( E\left(K_{n, m}\right)=\{1, \ldots, n+m\} \quad \) und \( \quad K\left(K_{n, m}\right)=\{\{i, j\} \mid i \leq n, j \geq n+1\} \)
Berechne den Grad jeder Ecke von \( K_{n, m} \). Wie viele Kanten hat \( K_{n, m} \) insgesamt?
Tipp: Zeichne zunächst die Graphen \( K_{n, m} \) für kleine Werte für \( n \) und \( m \). Als Beispiel sind hier die Graphen \( K_{1,4} \) und \( K_{2,3} \) abgebildet.

Wie soll man hier denn vorgehen ?

Answer 1

Es gibt zwei Arten von Knoten:

die n Knoten 1,...,n und die m Knoten n+1,...,n+m.

Jeder Knoten der ersten Art ist mit jedem Knoten der zweiten Art mit einer Kante

verbunden, d.h. zu jedem Paar (i,j) mit i=1,...,n und j=n+1,...,n+m gibt es eine

Kante {i,j}. Vielleicht ist es nun klarer?

Comments

Ja vielen Dank. Im Beispiel werden die Graphen K1,4 und K 2,3 dargestellt. Wurde bei beiden Graphen bewusst insgesamt 5 Knoten gewählt? Sollte ich mir jetzt als nächstes z.B. K 3,2 und K 4,1 anschauen um da ein Muster für die Rechnung zu erkennen ?

---

Kann ich die Rechnung für den Grad der Ecken so aufschreiben? :

Grad = G

G_E (K_n) = m   (Das wäre jetzt für den Grad der n- Ecken)

---

\(K_n\) hat eine andere Bedeutung, das wäre der vollständige Graph

mit n Ecken. Der Grad eines Knoten wird normalerweise mit \(deg\)="degree"

bezeichnet oder mit \(d(...)\)

Du meist sicher \(deg(1)=deg(2)=\cdots=deg(n)=m\) oder?

---

Um die Anzahl der Kanten anzugeben, musst du dir nur überlegen,

wieviele Paar \(\{i,j\}\) mit i=1,...,n und j=n+1,...,n+m

gebildet werden können. Das kann nicht schwer sein !

---

Im Prinzip kann doch die Anzahl der Kanten durch die Summe der deg(n)  oder deg (m) beschrieben werden also:

K (K_n,m) = ⁿ∑ _i=0  deg(n)   (Oder halt mit m)

Oder?

---

Das ist ja richtig, aber warum so komplizert?

Die Anzahl der Paare ist

\(|\{1,\cdots,n\}\times\{n+1,\cdots, n+m\}|=\)

\(|\{1,\cdots,n\}|\cdot |\{n+1,\cdots,n+m\}|=n\cdot m\)

---

Verstehe, danke für die Hilfe!