Die Mathe-Redaktion - 19.07.2018 19:05 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
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 Gäste und 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 » Graph mit: (Anzahl der Kantenzüge der Länge l)=l-te Fibonacci-Zahl
Druckversion
Druckversion
Autor
Universität/Hochschule J Graph mit: (Anzahl der Kantenzüge der Länge l)=l-te Fibonacci-Zahl
cptflint
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 80
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-06-23 13:59

\(\begingroup\)
Moin, moin,

ich frage mich gerade Folgendes: Man soll einen Multigraphen mit einem Knoten $v$ konstruieren, sodass die Anzahl der geschlossenen Kantenzüge der Länge $l$ beginnend in $v$ genau die $l$-te Fibonacci-Zahl ist.

Ich bezweifele, dass dies möglich ist, denn die Anzahl solcher Kantenzüge ist gegeben durch einen der Diagonaleinträge der Potenz einer Adjazenzmatrix. Also kann man folgenden Ansatz machen:
$\begin{pmatrix} 1&1\\1&0\end{pmatrix}^n = \begin{pmatrix} f_{n+1}&f_n\\f_n&f_{n-1}\end{pmatrix}$

Selbst wenn man nun die beiden Diagonaleinträge tauscht, auf der Diagonalen landet in der $n$-ten Potenz doch nie die $n$-te Fibonacci-Zahl, immer die $n+1$-te oder $n-1$-te, oder liegt da meienrseits ein Denkfehler vor?


Liebe Grüße
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 524
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-06-23 14:58

\(\begingroup\)
Hallo,

dürfen sich in einem geschlossenen Kantenzug Kanten wiederholen? Dürfen sich Knoten wiederholen?

Damit es genau einen geschlossenen Kantenzug der Länge 1 gibt, der bei $v$ startet, muss es eine Schlaufe bei $v$ geben, also einen Kantenzug $v-v$. Zählt dann $v-v-v$ als Kantenzug der Länge 2?

Und wenn es zwischen $v$ und $w$ eine Kante gibt, ist dann $v-w-v$ ein Kantenzug der Länge 2?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
cptflint
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 80
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-06-23 15:02

\(\begingroup\)
Hey,

ja Kanten dürfen sich wiederholen. Knoten ebenso, denn wenn man eine kante doppelt begeht, dann wiederholt man den Knoten ja auch.

Da wir einen Multigraphen konstruieren dürfen ist $v - v -v$ nicht ganz eindeutig, könnte ja sein, dass es fünf Schlaufen bei v gibt.
Wenn es zwichen $v$ und $w$ eine Kante gibt, dann ist $v-w-v$ in der Tat ein Kantenzug der Länge 2, ja.


\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 524
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-06-23 15:22

\(\begingroup\)
Wenn sich Kanten wiederholen dürfen, dann gibt es so einen Multigraphen wohl nicht:

Denn wenn es ihn gäbe, dann müsste es eine eindeutige Schlaufe bei $v$ geben (damit es genau $F_1=1$ geschlossene Kantenzüge der Länge 1 gibt).
Dann ist auch $v-v-v$ ein geschlossener Kantenzug der Länge 2. Gäbe es einen Knoten $w\not=v$ und eine Kante zwischen $w$ und $v$, dann wäre $v-w-v$ auch ein geschlossener Kantenzug der Länge 2. Also gäbe es mehr als $F_2=1$ geschlossene Kantenzüge der Länge 2. Folglich gibt es kein solches $w$, d.h. bei $v$ liegt außer der Schlaufe keine weitere Kante an.
Dann ist aber $v-v-v-v$ der einzige geschlossene Kantenzug der Länge 3, der bei $v$ startet. Es müsste aber $F_3=2$ solche geben.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
cptflint
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 80
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-06-23 15:23


Okay, dann habe ich keinen Denkfehler, Deine Argumentation läuft am Ende ja auch auf die Adjazenzmatrix hinaus, die es so nicht geben kann...


Vielen Dank :)



  Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1035
Aus: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-06-23 17:15


Ich weiß ja nicht, wo die Aufgabe herkommt, aber ich möchte kurz anmerken, dass es eine Lösung gibt, wenn man F_0=1 und F_1=1 als Start für "die" Fibonnaccifolge wählt statt 0 und 1. Ich weiß nicht, welche Variante die üblichere ist, aber es klingt so, als hätte der Aufgabensteller das im Kopf.

Es kann auch gar nicht anders sein, da es immer genau einen Pfad der Länge 0 gibt, also F_0=1 ist.


-----------------
"Eine Wissenschaft ist erst dann als voll entwickelt anzusehen, wenn sie dahin gelangt ist, sich der Mathematik bedienen zu können."
Karl Marx



  Profil  Quote  Link auf diesen Beitrag Link
cptflint
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 80
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-06-23 17:19


Das stimmt natürlich!

Ich habe mal zur Sicherheit nachgeschaut, der Aufgabensteller wählte

fed-Code einblenden


und damit gibt es dann wirklich keine Lösung...


Vielen Dank für die Anmerkung!



  Profil  Quote  Link auf diesen Beitrag Link
cptflint hat die Antworten auf ihre/seine Frage gesehen.
cptflint hat selbst das Ok-Häkchen gesetzt.
cptflint wird per Mail über neue Antworten informiert.
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-2018 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]