Tilman
63 lines
2.6 KiB
PHP
63 lines
2.6 KiB
PHP
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
|
|
<link rel="stylesheet" type="text/css" media="all" href="stylesheet.css">
|
|
<title>Graphen und Bäume</title>
|
|
</head>
|
|
<body>
|
|
<span id="menu"><a href="index.php">zurück zur Liste</a></span>
|
|
|
|
<div id="buttons">
|
|
<form action="edit.php" method="POST">
|
|
<input type="hidden" name="filename" value="<?php echo $_SERVER['SCRIPT_FILENAME']?>">
|
|
<p>
|
|
<input type="submit" value="Seite bearbeiten">
|
|
</p>
|
|
</form>
|
|
</div>
|
|
|
|
<h1>Graphen und Bäume</h1>
|
|
<div class="quelle">Grafiken entnommen aus Saake, Sattler: "Algorithmen & Datenstrukturen"</div>
|
|
|
|
<h2>Graphen</h2>
|
|
|
|
<h3>Gerichteter Graph</h3>
|
|
<img src="gerichtetergraph.gif"><br>
|
|
Als gerichteten Graph bezeichnet man einen Graph, der gerichtete Kanten enthält.<br><br>
|
|
|
|
<h3>Ungerichteter Graph</h3>
|
|
<img src="ungerichtetergraph.gif"><br>
|
|
Als ungerichteten Graph bezeichnet man einen Graph, der nur ungerichtete Kanten enthält. Dies schließt in der Regel auch Schleifen aus. Normalerweise gibt man den Zusatz <i>ungerichtet</i> nicht mit an, da man in der Regel meist nur ungerichteten Graphen meint, wenn man von Graphen spricht.<br><br>
|
|
|
|
<h3>Gewichteter Graph</h3>
|
|
<img src="gewichtetergraph.gif"><br>
|
|
Als gewichteter Graph bezeichntet man einen Graph, der Knoten- oder Kantengewichte hat.
|
|
<br><br>
|
|
|
|
<h3>Planarer Graph</h3>
|
|
Ein planarer Graph (auch plättbarer Graph) ist ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, so dass sich die Kanten nur in den Knoten schneiden.
|
|
<table>
|
|
<tr>
|
|
<td><b>Planarer Graph</b></td>
|
|
<td><b>Kein planarer Graph</b></td>
|
|
</tr>
|
|
<tr>
|
|
<td><img src="planarergraph.gif"></td>
|
|
<td><img src="nichtplanarergraph.gif"></td>
|
|
</tr>
|
|
</table><br>
|
|
|
|
<h3>Bipartiter Graph</h3>
|
|
<img src="bipartitergraph.gif"><br>
|
|
Ein Graph heißt bipartit (auch paar), falls seine Knoten sich in zwei Teilmengen aufteilen lassen (Bipartition), so dass es zwischen den Knoten innerhalb einer Teilmenge keine Kanten gibt. Damit sind die Teilmengen stabile Mengen und die Bipartition impliziert eine mögliche 2-Färbung des Graphen. Umgekehrt sind alle 2-färbbaren Graphen bipartit.<br><br>
|
|
|
|
|
|
|
|
<h2>Bäume</h2>
|
|
<a href="baeume.php">... weiter zu Bäume</a>
|
|
|
|
<h2>Links</h2>
|
|
<a href="http://www.vameo.de/uni/tutorium/graphen.pdf">Merkblatt zu Graphen von Augustin (u.a. Adjazenzliste, Adjazenzmatrix, Dijkstra, Prim, Krustal, ...)</a>
|
|
</body>
|
|
</html> |