Die Mathe-Redaktion - 23.11.2017 13:54 - Registrieren/Login
Auswahl
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 oder den Newsletter bestellen.

Der Newsletter Okt. 2017

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

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 

VerzeichnisLink vorschlagen Neue Links Meine Links Populäre Bestbewertet Neue Bewertungen Link der Stunde



Verzeichnis / Mathematik / Graphentheorie

Weitere Links-Unterkategorien
  • Traveling Salesman (6) 
  •  
    Arbeitsgruppe Alexandria 13 eigene Artikel zum Stichwort Graphentheorie:
     
    Listenfärbung [von Kobe]  
    ist ein noch relativ neuer Zweig in der Graphentheorie. Es geht nicht direkt um Färbung von Graphen, mehr um eine Verschärfung des Farbenproblems, mit dem man aber durchaus Probleme lösen kann. Zuerst, was heißt färbbar?
    Was ist ein Matroid? [von matroid]  
    Schon vor 2 Jahren hatte ich einen Artikel 'Was ist ein Matroid' geschrieben, der mir heute aber nicht mehr gefiel.Hier ist eine überarbeitet und erweiterte Fassung. Ich werde erklären, was ein Matroid ist, warum man sich damit beschäftigt und der Frage nachgehen, in welchem Sinne Matroide nützlich sind.
    Das Königsberger Brückenproblem - Beweistechnik+Graphentheorie [von matroid]  
    Mathematische Beweisprinzipien beim Königsberger Brückenproblem angewendet. Der berühmte Euler hat das Problem formuliert. Die Antwort verdeutlicht Begriffe wie "notwendige und hinreichende Bedingung" und es wird ein "indirekter Beweis" gegeben. Durch Java-Applets wird die Fragestellung verdeutlich
    Graphentheorie: Hamiltonkreise Teil 1 [von AimpliesB]  
    Ich moechte euch ein bisschen was ueber Hamiltonkreise erzaehlen, bzw. ueber Graphen und notwendige Bedingungen fuer die Existenz von Hamiltonkreisen. Deshalb zuerst eine kleine (wirklich kleine, ich erzaehl' nur das, was wir fuer die Hamiltonkreise brauchen) Einfuehrung in die Gr ...
    Der Fünffarbensatz [von Fabi]  
    Viele von euch haben bestimmt schon mal vom Vierfarbensatz gehört: Jede Landkarte lässt sich mit 4 Farben färben, so dass benachbarte Länder verschiedene Farben haben. Der Beweis dafür ist serh schwer. Für 5 Farben geht es aber einfacher, wie Fabi hier gezeigt hat.
    Gruppenwertige Flüsse [von Fabi]  
    Einführung in diese Interessante Verbindung von Gruppen- und Graphentheorie.
    5-Farben-Satz [von Kobe]  
    Dass jeder ebene Graph 5-färbbar ist, hat Fabi bereits hier bewiesen. Aber ich werde diesen Satz auf eine andere Art und Weise beweisen. Kombinatorischer und mit Listenfärbung
    Algebraische Topologie 1 [von Gockel]  
    Dieser Artikel stellt den ersten Teil der Serie Algebraische Topologie dar und führt mit motivierenden Beispielen in die Ideen einiger Konstruktionen aus der Alg.Topologie ein. Beispiele aus Analysis, Funktionentheorie, Kombinatorik und anderen Bereichen werden gegeben.
    To classify the Uncats - Mehr über Matroide [von jannna]  
    Gruppenzwang XIII: Amnestie: Auch Untergruppen frei [von Gockel]  
    Cayley-Graphen, Satz von Schreier-Nielsen
    kleine mathematische Hilfe für potentielle Schwiegermütter [von N-man]  
    Ein humorvoller Artikel über das Finden maximaler Matchings.
    Polyedersatz und Fermatsche Vermutung [von trunx]  
    Der Eulersche Polyedersatz, zur Erinnerung: e+f-k=2, sieht so einfach zu handhaben aus, aber schon bei der Anwendung auf ein Dreieck scheint man zu versagen: 3 Ecken, 3 Kanten, 1 Fläche ergibt hartnäckig: 3+1-3=1 und nicht 2. Die unten angegebene Figur 1 wird oft zum Beweis des Sat
    Warum wohnt der Nikolaus nicht im Bungalow? [von jannna]  
    Etwas über Graphentheorie - Vier-Farben-Satz, Kantenfärbungen, Snarks, Petersen-Graphen und die Äquivalenz gewisser Färbungs- und Flußprobleme auf kubischen Graphen.
    Externe Seiten


    Sortieren nach:  Titel .oO Oo. Datum .oO Oo. Bewertung .oO Oo. Popularität .oO Oo.
    Einträge sind sortiert nach: Titel (A bis Z)


    Counting Hamilton cycles in product graphs  Populär
    Beschreibung: Entwicklung einer wissenschaftlichen Arbeit von erster Leidenschaft bis zur Veröffentlichung.
    Über die Zählung aufspannender Bäume und der Hamilton-Kreise in allgemeinen und speziellen Graphen mit linearen ganzzahligen Rekursionen.
    Nützlich: Überblick der Graphen, für die solche Berechnungsmethoden bekannt sind, in einer Tabelle.
    Auf englisch.

    Eingefügt am 27 09 2001 Hits: 812
    Selbst bewerten | DetailsUngültigen Link mitteilenUrl/Beschreibung ändern
    Kategorie: Mathematik / Graphentheorie

    Das Königsberger Brückenproblem  Populär
    Beschreibung: Mathematische Beweisprinzipien beim Königsberger Brückenproblem angewendet. Der berühmte Euler hat das Problem formuliert. Die Antwort verdeutlicht Begriffe wie "notwendige und hinreichende Bedingung" und es wird ein "indirekter Beweis" gegeben.
    Durch Java-Applets wird die Fragestellung verdeutlicht und wird der "Leser" auf die richtigen Ideen zur Lösung gebracht.
    Mit dieser Aufgabe hat Euler die Graphentheorie begründet
    Die Link führt auf die Seiten der Bergischen Universität Wuppertal.

    Eingefügt am 05 04 2001 Hits: 3870 Bewertung: 8.00 (5 Stimmen)
    Selbst bewerten | Frühere BewertungenUngültigen Link mitteilenUrl/Beschreibung ändern
    Kategorie: Mathematik / Graphentheorie

    Einführung in Graphen und Algorithmen:  Populär
    Beschreibung: Ein online-Buch, 450 Seiten, aufgeteilt in mehrere .ps-Files. Von Thomas Emden-Weinert et.al.
    1 Einführung (51 Seiten, 656kB)
    1.1    Grundlegende Begriffe
    1.1.1  Partite Graphen
    1.1.2  Operationen auf Graphen
    1.1.3  Bäume, Artikulationen, Schnitte
    1.1.4  Zufällige Graphen
    1.2    Die Komplexität von Algorithmen
    1.2.1  Entscheidbarkeit
    1.2.2  Die Klasse P oder: zugängliche Probleme
    1.3    Algorithmische Prinzipien
    1.3.1  Breiten- und Tiefensuche
    1.3.2  Dynamisches Programmieren: das kürzeste-Wege-Problem
    1.3.3  Greedy: minimale aufspannende Bäume
    1.4    Die Klasse NP oder: polynomielle Verifizierbarkeit
    1.4.1  NP-Vollständigkeit
    1.4.2  NP-schwere Probleme und Optimierung
    1.5    Zum Umgang mit NP-schweren Problemen: Algorithmen für Independent Set
    
    2 Netzwerkflüsse und Zusammenhang (22 Seiten, 569kB)
    2.1    Der Markierungsalgorithmus von Ford und Fulkerson
    2.2    Der Satz von Menger nebst Folgerungen
    2.3    2-Zusammenhang, Blockstruktur und Tiefensuche
    2.4    Die Zusammenhangszahlen
    
    3 Durchlaufbarkeit (13 Seiten, 323kB)
    3.1    Eulersche Graphen
    3.2    Hamiltonsche Graphen
    
    4 Matching (34 Seiten, 500kB)
    4.1    Die Sätze von Berge und Gallai
    4.2    Matching in bipartiten Graphen
    4.3    Matching in allgemeinen Graphen
    
    5 Färbung (39 Seiten, 1076kB)
    5.1    Die chromatische Zahl
    5.2    Greedy-Färbung und der Satz von Brooks
    5.3    Chromatische Zahl und Taillenweite
    5.4    Die Komplexität des Färbungsproblems
    5.5    Färbungsalgorithmen
    5.6    Kantenfärbung: der Satz von Vizing
    5.7    Kantenfärben in bipartiten Graphen
    
    6 Topologische Graphentheorie (58 Seiten, insgesamt 3.886kB, Teil 1, Teil 2, Teil 3, Teil 4)
    6.1    Planare Graphen
    6.1.1  Ebene Graphen
    6.1.2  Die Eulersche Formel
    6.1.3  Die Sätze von Kuratowski und Wagner
    6.1.4  Dualität bei planaren Graphen
    6.2    Ein Einbettungsalgorithmus [Fragment]
    6.3    Die 4-Farben-Vermutung
    6.4    Graphen höheren Geschlechts
    6.5    Der 4-Farben-Satz und Komplexitätsfragen
    6.6    Kreuzungszahl, Dicke, Arborizität und Buchdicke
    
    7 Perfekte Graphen (23 Seiten, 314kB)
    7.1    Einleitung
    7.2    Chordale Graphen
    7.3    Vergleichbarkeitsgraphen
    7.4    Intervallgraphen [Fragment]
    7.5    Graphen mit perfekter Ordnung [Fragment]
    7.6    Im Umfeld der Perfekte-Graphen-Vermutung [Fragment]
    7.7    Optimierung auf perfekten Graphen [Fragment]
    
    8 Separatoren (22 Seiten, 569kB)
    8.1    Einleitung
    8.2    Separatoren in planaren Graphen
    8.3    Independent Set auf planaren Graphen
    8.4    Separatoren für andere Graphenklassen
    8.5    Cliquenseparatoren
    
    9 Baumweite (10 Seiten, 206kB)
    9.1    Baumweite und k-Bäume
    9.2    Optimierung auf Graphen beschränkter Baumweite
    9.3    Randomisierung I: Subgraph Isomorphismus [Fragment]
    
    10 Approximationsalgorithmen (42 Seiten, 1067kB)
    10.1   Einleitung
    10.2   Knotenüberdeckung
    10.3   Steiner-Bäume
    10.4   Das Traveling Salesman Problem
    10.5   Das Zentrumsproblem
    10.6   Randomisierung II: Max Cut und Max Sat
    10.7   Lokale Verbesserung
    10.8   Ein PAS für Planar Independent Set
    10.9   Graph Coloring und Independent Set
    
    11 Nicht-Approximierbarkeit (2 Seiten, 86kB)
    11.1   MAX-SNP und PCP [Fragment]
    11.2   Clique [Fragment]
    11.3   Graph Coloring [Fragment]
    
    12 Überdeckungsprobleme (29 Seiten, 427kB)
    12.1   Cliquenüberdeckung und Schnittgraph-Darstellung
    12.2   Erkennung von Linegraphen [Fragment]
    12.3   Primal-dual Approximationsalgorithmen
    12.3.1 Der primal-dual Algorithmus der Linearen Optimierung
    12.3.2 Hitting Set, Node Cover und Dominating Set
    12.3.3 Shortest Path
    12.3.4 Das Generalized Steiner Tree Problem
    12.3.5 Survivable Network Design mit Mehrfachkanten
    12.4   Approximation von Set Cover und Dominating Set
    
    13 Zufällige Graphen und probabilistische Algorithmen (16 Seiten, 273kB)
    13.1   Die Cliquenzahl
    13.2   Die chromatische Zahl
    
    14 Ein Blick in die extremale und asymptotische Graphentheorie (14 Seiten, 669kB)
    14.1   Die Sätze von Turan und von Erdös und Stone
    14.2   Fast alle dreiecksfreien Graphen sind bipartit
    14.3   Mehr über dreiecksfreie Graphen
    
    A Anhang (20 Seiten, 255kB)
    A.1    Grundbegriffe der Wahrscheinlichkeitstheorie
    A.2    Hinweise und Lösungen zu ausgewählten Übungen
    A.3    Die Grenze zwischen P und NP-vollständig
    A.4    Übersicht über Graphenparameter
    A.5    Weiterführende Literatur
    
    Literaturverzeichnis (46 Seiten, 335kB)
    
    Entstanden 1996 an der Humboldt-Universität zu Berlin, Institut für Informatik, Lehrstuhl für Algorithmen und Komplexität

    Eingefügt am 26 10 2004 Hits: 1309
    Selbst bewerten | DetailsUngültigen Link mitteilenUrl/Beschreibung ändern
    Kategorie: Mathematik / Graphentheorie

    Eulersche Polyederformel 
    Beschreibung: "Grundlage für viele Herleitungen in der Graphentheorie ist die Eulersche Polyederformel, die wir hier beweisen. Nachfolgend geben wir noch eine anschauliche Anwendung dieses wichtigen Satzes bei der Fünf-Länder-Regel."
    Ein Beitrag von www.mathematik-online.de.

    Eingefügt am 08 11 2004 Hits: 797 Bewertung: 5.00 (1 Stimme)
    Selbst bewerten | Frühere BewertungenUngültigen Link mitteilenUrl/Beschreibung ändernKommentare (1)
    Kategorie: Mathematik / Graphentheorie

    Graphenalgorithmen  Populär
    Beschreibung: Vorlesung gehalten im WS 1996/97 von Oliver Vornberger, Fachbereich Mathematik/Informatik, Universität Osnabrück.
    Inhalt:
         1 Einführung 
              1.1 Modellierungsmöglichkeiten von Graphen 
              1.2 Grundtypen bei der Zielfindung 
              1.3 Lösungsstrategien 
         2 Implementation von Graphen 
         3 Zusammenhangskomponenten 
              3.1 Artikulationspunkt 
              3.2 2-fach zusammenhängend 
         4 Union/Find 
              4.0.1 Satz von Tarjan 
              4.0.2 Path Halving 
         5 Minimum Spanning Tree 
              5.1 Algorithmus von Kruskal 
              5.2 Algorithmus von Prim 
         6 Kürzeste Wege Probleme 
              6.1 Algorithmus von Dijkstra 
              6.2 Strenge Zusammenhangskomponenten 
              6.3 Transitiver Abschluß 
              6.4 All pairs shortest path 
                   6.4.1 Algorithmus von Floyd 
              6.5 Pert 
         7 Location-Probleme 
              7.1 Zentrum 
                   7.1.1 Generelles Zentrum 
                   7.1.2 Absolutes Zentrum 
                   7.1.3 Absoluter Median 
                   m -Zentrum 
         8 Maximale Flüsse Probleme 
              8.1 Fluß 
              8.2 Erweiternder Weg 
              8.3 Algorithmus von Ford-Fulkerson 
              8.4 Cut 
         9 Kostenminimale Flüsse 
              9.1 Erweiternder Kreis 
         10 Matching 
              10.1 Maximum/maximales Matching 
              10.2 Bipartiter Graph 
              10.3 Erweiternder Weg 
              10.4 (Erweiternder) alternierender Baum 
              10.5 2-Prozessor Scheduling 
              10.6 Vertexcover 
              10.7 Independent Set 
              10.8 Perfektes Matching 
              10.9 Heiratsproblem 
         11 Traveling Salesman 
              Hamiltonkreis 
                   Exakte Lösungen für das TSP 
              Näherungslösungen für das TSP 
         12 Begriff der NP-Vollständigkeit 
         13 Näherungslösung für das Vertexcover Problem 
         14 Chinese Postman 

    Eingefügt am 09 09 2001 Hits: 2140 Bewertung: 6.33 (3 Stimmen)
    Selbst bewerten | Frühere BewertungenUngültigen Link mitteilenUrl/Beschreibung ändern
    Kategorie: Mathematik / Graphentheorie

    Graphenalgorithmen  Populär
    Beschreibung: - Darstellung von Graphen, Adjazenz-Listen, Adjazenz-Matrizen
    - Durchwandern von Graphen
    - Topologisches Sortieren
    - Minimale aufspannende Bäume
    - Kürzeste Wege
    Von Oliver Vornberger, Osnabrück.

    Eingefügt am 14 06 2002 Hits: 1163 Bewertung: 8.00 (1 Stimme)
    Selbst bewerten | Frühere BewertungenUngültigen Link mitteilenUrl/Beschreibung ändern
    Kategorie: Mathematik / Graphentheorie

    Graphentheoretische Methoden und Algorithmen  Populär
    Beschreibung: Übungen mit Lösungen zur Vorlesung.
    Inhalte: Gerichtete Graphen, Wege, Kreise und Zusammenhang, Satz von Euler, Hamiltonsche Kreise, Transitive Hülle und irreduzible Kerne (Der Tripelalgorithmus - Der Reduzierte Graph - Irreduzible Kerne), Bäume, Wälder und Matroide, Minimal spannende Bäume, Steinerbäume, Suchstrategien (Tiefensuche, DFS, Breitensuche), kürzeste Wege, Dijkstra, Bellman und Ford, Flüsse, Max-Flow-Min-Cut Theorem - Der Algorithmus von Ford und Fulkerson, Eulersche Polyederformel, Triangulationen, Graphtransformationen

    Eingefügt am 16 06 2002 Hits: 1676 Bewertung: 3.00 (1 Stimme)
    Selbst bewerten | Frühere BewertungenUngültigen Link mitteilenUrl/Beschreibung ändern
    Kategorie: Mathematik / Graphentheorie

    Graphentheorie  Populär
    Beschreibung: Aus einem Seminar an der Humboldt-Universität zu Berlin.
    Zitat: "In dieser Sitzung werden mathematische Grundbegriffe eingeführt, um die Topologie von Netzen zu beschreiben."
    Definitionen und Beispiele als Basis für Netzwerksflußprobleme.
    Suchworte: Satz von Ford-Fulkerson (max flow = min cut), Satz von Menger, Digraphen, Bäume, Bipartite Graphen, Vollständiger Graph, Handschlaglemma.

    Eingefügt am 09 09 2001 Hits: 1234
    Selbst bewerten | DetailsUngültigen Link mitteilenUrl/Beschreibung ändern
    Kategorie: Mathematik / Graphentheorie

    Kombinatorik und Graphen  Populär
    Beschreibung: Inhalt: Schlichte/ebene Graphen, Eulersche Polyederformel, Königsberger Brückenproblem, Bäume, reguläre/binäre Wurzelbäume.
    Skript (pdf) von Prof. B. Pareigis, Uni München.

    Eingefügt am 14 06 2002 Hits: 1024
    Selbst bewerten | DetailsUngültigen Link mitteilenUrl/Beschreibung ändern
    Kategorie: Mathematik / Graphentheorie

    Kritische Analyse von Routensuchverfahren  Populär
    Beschreibung: Zitat aus der Einleitung: "Routensuchverfahren können zu den wichtigsten grundlegenden Algorithmen in den Modellen des Verkehrswesens gezählt werden. Mit ihrer Hilfe werden optimale Wege für den Wechsel von Verkehrsteilnehmern und -gütern zwischen Orten innerhalb eines Verkehrsnetzes bezüglich eines vorgegebenen Kriteriums ermittelt. Solche Ortswechsel bilden die Basis des Verkehrs und somit einer Vielzahl von Verkehrsmodellen. [...] In der Graphentheorie werden Routensuchverfahren "Algorithmen zur Bestimmung kürzester Wege" genannt. Sie zeichnen sich durch ihre vielseitige Anwendbarkeit in beliebigen Bereichen aus, in denen das topologische Problem der Suche optimaler Wege auftritt. So lassen sich beispielsweise in Kommunikationsnetzen die bestmöglichen nicht direkten Schaltungen von Ferngesprächen über mehrere Städte ermitteln, die effektivste Nutzung eines Roboters zum Löten von Platinen herleiten oder der minimale Verbrauch an Kabeln für die Versorgung eines Hochhauses bestimmen. Für den effizienten Einsatz von Parallelrechnern und für schnelles Editieren in Graphiksystemen bilden Kürzeste-Wege-Algorithmen eine Grundlage. In der Graphentheorie treten die Algorithmen zur Bestimmung der kürzesten Wege oft auch als Teil eines anderen Verfahrens auf. Als praktisches Beispiel sei hier die optimale Beladung eines Containerseeschiffes erwähnt, das auf einer möglichst kurzen Rundreise seine Fracht in einer Vielzahl von Häfen unterschiedlicher Länder möglichst schnell entladen soll."
    Sehr gute Studienarbeit im pdf-Format von Martin Rose.

    Eingefügt am 09 09 2001 Hits: 876 Bewertung: 6.33 (3 Stimmen)
    Selbst bewerten | Frühere BewertungenUngültigen Link mitteilenUrl/Beschreibung ändernKommentare (1)
    Kategorie: Mathematik / Graphentheorie


    Seite: 1 2  [Nächste] 
    -> Bücher zu 'Graphentheorie' bei amazon.dei

     
    All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 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]