Mathematik HTL 4/5, Schulbuch

298 Zusammenfassung: Diskrete Mathematik Ein Graph heißt zusammenhängend, wenn es von jeder seiner Ecken einen Weg zu jeder anderen gibt. Ein Graph U ist ein Untergraph eines Graphen G, wenn alle Ecken bzw. Kanten von U auch Ecken bzw. Kanten von G sind. Ein Minimalgerüst eines bewerteten Graphen ist ein zusammenhängender Untergraph mit der- selben Eckenmenge so, dass die Summe der Bewertungen aller Kanten des Untergraphen mög- lichst klein ist. Mit dem Algorithmus von Prim kann ein Minimalgerüst ermittelt werden. Ein Graph, in dem es von jeder Ecke zu jeder anderen Ecke genau einen Weg gibt, heißt Baum . Mit dem Algorithmus von Dijkstra werden für eine Ecke a in einem mit positiven Zahlen bewer- teten Graphen die kürzesten Wege von a nach allen anderen Ecken in diesem Graphen ermittelt. Der Grad einer Ecke a ist die Anzahl der Kanten, die a als Eckpunkt haben. Ein (n + 1)-Tupel von Ecken (a 0 , a 1 , …, a n ) eines Graphen heißt Kantenzug, wenn die Kanten [a 0 , a 1 ], [a 1 , a 2 ], …, [a n – 1 , a n ] paarweise verschieden sind. Ein Eulerweg ist ein Kantenzug, in dem alle Kanten des Graphen vorkommen. Eine Eulertour ist ein Eulerweg, bei dem die erste und die letzte Ecke gleich sind. In einem Graphen gibt es genau dann eine Eulertour , wenn die Grade aller seiner Ecken gerade sind. Einen Eulerweg gibt es genau dann, wenn der Graph höchstens 2 ungerade Ecken enthält. Gibt es genau zwei ungerade Ecken, muss eine davon der Start und die andere das Ende des Kanten- zugs sein. Eine Schaltung besteht aus mehreren Schaltern, Leitungen und einem Verbraucher, an dem man sieht, ob Strom fließt oder nicht. Diese zwei möglichen Zustände des Verbrauchers beschreiben wir durch die Zahlen 0 (Strom fließt nicht) und 1 (Strom fließt), ebenso die zwei möglichen Zustände der Schalter. Eine Schaltfunktion ist eine Funktion von {0, 1} n nach {0, 1}, die jedem Zustand von n Schaltern einer gegebenen Schaltung den entsprechenden Zustand des Verbrauchers zuordnet. Jede Schaltfunktion f: {0, 1} n ¥ {0, 1} kann in disjunktiver bzw. in konjunktiver Normalform ange- schrieben werden. Sie ermöglichen es, zu einer gegebenen Schaltfunktion die entsprechende Schaltung als Parallelschaltung von Serienschaltungen bzw. Serienschaltung von Parallelschal- tungen anzugeben. Eine lineare Optimierungsaufgabe mit zwei Unbekannten ist gegeben durch ein System linearer Ungleichungen mit zwei Unbekannten, dessen Lösungsmenge heißt zulässiger Bereich , und eine lineare Funktion Z von R 2 nach R , diese heißt Zielfunktion . Ein optimaler Punkt ist ein Zahlenpaar im zulässigen Bereich, dessen Funktionswert bezüglich Z möglichst groß ist. Wenn ein optimaler Punkt existiert, können wir diesen graphisch bestimmen, indem wir die Gerade {(a, b) ‡ Z(a, b) = 0} so lange in Richtung wachsender Funktionswerte von Z parallel verschieben, wie noch ein Punkt des zulässigen Bereichs auf dieser Geraden liegt. zusammenhän- gender Graph Untergraph Minimalgerüst Algorithmus von Prim Baum Algorithmus von Dijkstra Grad einer Ecke Eulerweg, Eulertour Schaltung Schaltfunktion disjunktive und konjunktive Normalform einer Schalt- funktion lineare Optimierungs- aufgabe Nur zu Prüfzwecken – Eigentum des V rlags öbv