Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Gleichung für Summe über Kantengewichte
Druckversion
Druckversion
Autor
Universität/Hochschule J Gleichung für Summe über Kantengewichte
Newmath2012
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.09.2013
Mitteilungen: 405
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-12-10


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!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4577
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-12-10


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$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.09.2013
Mitteilungen: 405
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-12-10


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.  



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.09.2013
Mitteilungen: 405
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-12-10


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)$



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4577
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-12-10


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?
 

 
Vielleicht liefert das Stichwort beim Suchen bessere Treffer.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4577
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-12-10


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Newmath2012 hat die Antworten auf ihre/seine Frage gesehen.
Newmath2012 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]