Forum:  Graphentheorie
Thema: Gleichung für Summe über Kantengewichte
Themen-Übersicht
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 380
Aus:
Themenstart: 2019-12-10 01:20

Hallo allerseits, es geht um ungeordnete, aufsteigende (also die Kinder haben größere Labels als die Eltern) Wurzelbäume.
Sei T ein solcher Baum mit Knotenmenge $\{1, ..., r\}$. Bezeichne $h_T(v)$ die Menge bestehend aus allen Nachfolgerknoten von v (also auch Enkelknoten, Urenkelknoten etc) und v selbst.
$y_{v,u}$ seien formale Variablen, die für die Kantengewichte von v nach u stehen.
Dann gilt: $\prod \limits_{v=2}^{r} \sum \limits_{u \in h_T(v)} y_{v, u} = \sum \limits_{g: \{2, ..., r\} \rightarrow \{2, ..., r\} \\ \forall u \in \{2, ..., r\}: g(u) \in h_T(u)} \prod \limits_{i \in \{2, ..., r\}} y_{i, g(i)}$
Meine Frage ist nun, wie man sich überlegen kann, dass diese Gleichheit gilt. Ich habe mir schon für r = 2, r = 3 und r = 4 aufgeschrieben, wie jeweils die linke und rechte Seite aussieht und daran gesehen, dass für diese Werte von r die Gleichheit tatsächlich gilt. Mir ist allerdings trotzdem nicht klar, wie man sieht, dass sie eben generell gilt.
Würde mich über eine Erklärung dazu sehr freuen, danke im Voraus!


Triceratops
Aktiv
Dabei seit: 28.04.2016
Mitteilungen: 4319
Aus: Berlin
Beitrag No.1, eingetragen 2019-12-10 01:32

Das ist einfach ein verallgemeinertes Distributivgesetz. Entsprechend hat das Problem auch nichts mit Graphentheorie zu tun, sondern ist elementare Algebra. Die allgemeine Formel ist:

$\displaystyle (\ast) \quad  \prod_{\large{i \in I}} \left( \sum_{\large{j \in S_i}} x_{i,j} \right) = \sum_{\large{g \in \prod_{i \in I} S_i}} \left(\prod_{\large{i \in I}} x_{i,g(i)}\right)$

Hierbei sind $x_{i,j}$ jeweils Elementes eines Ringes (zum Beispiel ganze Zahlen), $I$ eine endliche Menge, $S_i$ für jedes $i \in I$ eine endliche Menge.
 
Wenn man zum Beispiel $(a+b)(c+d)$ ausmultipliziert, muss man jeden Summanden des ersten Produktes mit jedem Summanden des zweiten Produktes multiplizieren, und dann alles summieren. Wenn man allgemeiner $(a+b+...)(c+d+...)(e+f+...)...$ ausmultipliziert, muss man jeden Summanden des ersten Produktes mit jedem Summanden des zweiten Produktes mit jedem Summanden der dritten Produktes usw. multiplizieren, und dann alles summieren.

Die Abbildung $g$ in der Formel sagt nur aus, welchen Summanden man jeweils in den Produkten ausgewählt hat.

Formal beweist man $(\ast)$ durch Induktion nach $\# I$ und den $\# S_i$.


Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 380
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2019-12-10 14:48

Hallo Triceratops,
vielen Dank! Da war ich mit meinen Erklärungsversuchen auf dem Holzweg...
Wieso ist bei uns aber erfüllt, dass die Variablen einen Ring bilden? Sie haben doch nicht alle inverse Elemente?
Hast du vielleicht auch einen Link, wo ich dieses allgemeine Distributivgesetz nachlesen kann? Ich habe es via Google leider bislang nicht gefunden.  


Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 380
Aus:
Beitrag No.3, vom Themenstarter, eingetragen 2019-12-10 16:05

Hallo Triceratops,
ich habe dazu noch eine ganz ähnliche Umformung, die sich vmtl. auch mit dem Distributivgesetz erklären lässt. Ich sehe nur leider nicht, wie, und wäre froh, wenn du Licht ins Dunkel bringen könntest:

$\prod \limits_{i=2}^{r-1}\left(y_{i,i} \frac{x_1 + \dotsc + x_i}{x_i} + \sum \limits_{j = i+1}^{r}y_{i,j}\right) = \sum \limits_{g: \{r, \dotsc r-1\} \rightarrow \{2, \dotsc, r\} \\ \forall u \in \{2, \dotsc r-1\}: g(u) \geq u} \left( \left( \prod \limits_{i \in \{2, \dotsc, r-1\}\\g(i) > i} y_{i, g(i)} \right) \cdot \left(\prod \limits_{i \in \{2, \dotsc, r-1\}: \\g(i) = i}y_{i,i} \frac{x_1 + \dotsc + x_i}{x_i}\right)\right)$


Triceratops
Aktiv
Dabei seit: 28.04.2016
Mitteilungen: 4319
Aus: Berlin
Beitrag No.4, eingetragen 2019-12-10 21:44

2019-12-10 14:48 - Newmath2012 in Beitrag No. 2 schreibt:
Hallo Triceratops,
vielen Dank! Da war ich mit meinen Erklärungsversuchen auf dem Holzweg...
Wieso ist bei uns aber erfüllt, dass die Variablen einen Ring bilden? Sie haben doch nicht alle inverse Elemente?

Wenn du so willst, spielt sich hier alles im Polynomring über die $y_{v,u}$ ab. Aber es stimmt schon, dass man keine additiven Inversen braucht, man könnte auch einfach im Polynomhalbring (also Koeffizienten sind aus $\IN$) arbeiten.
 

Hast du vielleicht auch einen Link, wo ich dieses allgemeine Distributivgesetz nachlesen kann?
 
en.wikipedia.org/wiki/FOIL_method#Generalizations
 
Vielleicht liefert das Stichwort beim Suchen bessere Treffer.


Triceratops
Aktiv
Dabei seit: 28.04.2016
Mitteilungen: 4319
Aus: Berlin
Beitrag No.5, eingetragen 2019-12-10 21:47

2019-12-10 16:05 - Newmath2012 in Beitrag No. 3 schreibt:
Hallo Triceratops,
ich habe dazu noch eine ganz ähnliche Umformung, [...]
 
Ja, das folgt auch aus dem allgemeinen Distributivgesetz.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=244796=7080
Druckdatum: 2020-02-20 16:22