12.7. Graphentheorie

Letztmalig dran rumgefummelt: 02.02.15 19:52:44

	Etwas ganz einfaches kann sehr schnell sehr kompliziert und vor allem auch komplex werden - und dies ist nicht jeweils das selbe ;-) Die Graphentheorie versteckt sich hinter ziemlich vielen Computerproblemen aber auch ganz praktische Anwendungen lassen sich auf eben diese zurück führen. Es gibt Berührungspunkte zu fast allen Bereichen der Informatik - Netzwerktechnik sowie Programmablaufpläne sind nur zwei ganz schnell genannte und auch bekannte Repräsentanten.
	1. Graphentheorie - Begriffe und Festlegungen 2. Definitionen 3.Mathematische Prinzipien 5. Verwandte Themen
	die Informatikseiten Graphentheorie-Logo begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Graphentheorie - eine anwendungsoriientierte Einführung Seite 17 ff Technische und Theoretische Informatik  Seite ???

1. Graphentheorie - Begriffe und Festlegungen

	Ein Graph ist ein anschauliches mathematisches Modell zur Beschreibung von Objekten, die untereinander gewisse Beziehungen können. Er ist die ungerichtete oder auch gerichtete Verbindung (Kante) zwischen zwei Punkten (Knoten). Das nachfolgende basiert auf einem Fachvortrag von Prof. Tittmann, Hochschule für Technik und Wirtschaft Mittweida.
	Graphentheorie - Grundlagen und Begriffe Allgemeines Netzwerk - so verwendet von vielen naturwissenschaftlichen sowie technischen Disziplinen Graphentheorie ganz einfach ;-) die Adjazenzmatrix eines Grapehn gegebenes Graphensystem Weg in einem gegebenes Graphensystem Kreis  in einem gegebenes Graphensystem Baumstruktur vollständige Graphen planare Graphen nichtplanare Graphen
	Graphentheorie in der Anwendung - Rundreiseproblemematik und Knotenverbindungen Ausgangspunkt für das Rundreiseproblem eine mögliche Lösung Rundreise für Sachsen exakte Lösung unmöglich - es existieren 45 651 133 223 206 551 617 074 619 Möglichkeiten größtes bisher gelöstes Rundreiseproblem gegebenes Graphensystem ein zugehöriges Minimalgerüst gegebenes Graphensystem mit gesuchten kürzesten Verbindungen Zahlenangaben verstehen sich als Entfernungsangaben kürzeste Verbindung Zahlenangaben verstehen sich als Entfernungsangaben
	Graphentheorie in der Anwendung - Optimierungsprobleme Projektphasen   Projektplanung   Matching in bipartiten Graphen   Matching in bipartiten Graphen   das Maximalflussproblem Zahlenangaben verstehen sich als maximale Duchlasskapazität das Maximalflussproblem Zahlenangaben verstehen sich als maximale Duchlasskapazität Bewetterungsschächte im Bergbau Bewetterungsschächte im Bergbau
	Graphentheorie in der Anwendung - Ausfallsicherheit Ausfallwahrscheinlichkeit in Kommunikationsnetzen Ausfallwahrscheinlichkeit in Kommunikationsnetzen Ausfallwahrscheinlichkeit in Kommunikationsnetzen
	Graphentheorie in der Anwendung - Minimierungsfälle gegebenes Mobilfunknetz zugehörige Überlappungsbereiche der Sender Darstellung als Knoten Verbindung zum Graphen Minimale Einfärbung - sprich: Vergabe der Frequenzbänder resultierende Kanalzuordnung
	Graphentheorie in der Anwendung - Laufzeitoptimierung und Zeitkomplexität das ist Komplexität die Zusammenhänge zwischen den Faktoren die Zusammenhänge zwischen den Faktoren NP-vollständigen Probleme
	Graphentheorie in der Anwendung - das Internat als Graphenproblem Internet-Technik dezentrale Rechnerstruktur dezentrale Rechnerstruktur ARPANET

2. Definitionen

	Wie jedes Gebiet der Wissenschaft hat auch die Graphentheorie ihren eigenen Sprachgebrauch. Wir wollen in diesem Abschnitt die wichtigsten Grundbegriffe bereitstellen. Ein ungerichteter Graph G = (V E) besteht aus einer Knotenmenge V und einer Kantenmenge E, wobei jeder Kante e E E von G zwei (nicht notwendig verschiedene) Knoten aus V zugeordnet sind. Die Bezeichnungen V und E für die Knoten- und Kantenmenge eines Graphen kommen von den englischen Wörtern vertex (Knoten) und edge (Kante). Die Anzahl der Knoten und Kanten eines Graphen werden wir häufig mit n beziehungsweise m bezeichnen. Wir beschreiben eine Kante in der Form e = {u, v} wobei u und v die Endknoten der Kante e sind. Wenn v ein Endknoten der Kante e ist, so sagen wir auch v ist inzident zu e. Ein ungerichteter Graph G = (V E) heißt endlich, wenn die Mengen V und E endlich sind. Wir werden in diesem und den folgenden Kapiteln ausschließlich endliche ungerichtete Graphen betrachten, die wir deshalb auch kurz Graphen nennen. Im Gegensatz dazu gibt es auch gerichtete Graphen, die jedoch erst später eingeführt werden. Gerichtete Graphen enthalten Kanten, die zusätzlich einen Richtungssinn aufweisen. Auf diese Weise können zum Beispiel Straßennetze mit Einbahnstraßen modelliert werden. Die Zugehörigkeit einer Knotenmenge V und einer Kantenmenge E zu einem Graphen G werden wir auch durch die Schreibweise V(G) bzw. E(G)

3. Mathematische Prinzipien

5. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze Traversierungs-Probleme Baumstrukturen Turingmaschine
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im Mai 2007