Die Mathe-Redaktion - 29.01.2020 15:37 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktZur Award-Gala
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 703 Gäste und 17 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
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 Monat
Dabei seit: 26.09.2013
Mitteilungen: 380
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!



  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4278
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$.



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 380
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.  



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.09.2013
Mitteilungen: 380
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)$



  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4278
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?
 
en.wikipedia.org/wiki/FOIL_method#Generalizations
 
Vielleicht liefert das Stichwort beim Suchen bessere Treffer.



  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4278
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.



  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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]