Antworte auf:  Gleichung für Summe über Kantengewichte von Newmath2012
Forum:  Graphentheorie, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Triceratops
Aktiv
Dabei seit: 28.04.2016
Mitteilungen: 4569
Herkunft: Berlin
 Beitrag No.5, eingetragen 2019-12-10 21:47    [Diesen Beitrag zitieren]

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.


Triceratops
Aktiv
Dabei seit: 28.04.2016
Mitteilungen: 4569
Herkunft: Berlin
 Beitrag No.4, eingetragen 2019-12-10 21:44    [Diesen Beitrag zitieren]

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.


Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 405
Herkunft:
 Beitrag No.3, eingetragen 2019-12-10 16:05    [Diesen Beitrag zitieren]

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


Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 405
Herkunft:
 Beitrag No.2, eingetragen 2019-12-10 14:48    [Diesen Beitrag zitieren]

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.  


Triceratops
Aktiv
Dabei seit: 28.04.2016
Mitteilungen: 4569
Herkunft: Berlin
 Beitrag No.1, eingetragen 2019-12-10 01:32    [Diesen Beitrag zitieren]

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: 405
Herkunft:
 Themenstart: 2019-12-10 01:20    [Diesen Beitrag zitieren]

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!


 
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]