:: wikimiki.org ::

Unabhängigkeitszahl

Unabhängigkeitszahl

Definitionen

Sei G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und U eine Teilmenge von V. Man bezeichnet U als Clique von G, wenn für je zwei beliebige verschiedene Knoten v und w aus U gilt, dass sie durch eine Kante miteinander verbunden sind. Gilt hingegen stets für je zwei beliebige verschiedene Knoten v und w aus U, dass sie nicht benachbart sind, so nennt man U eine stabile bzw. unabhängige Menge (Independent Set) von G. Enthält jede Kante von E einen Knoten aus U, so nennt man U eine Knotenüberdeckung von G. Eine Clique bzw. stabile Menge U von G nennt man maximal, wenn man keinen weiteren Knoten v aus V zu U hinzufügen kann, so dass U zusammen mit v eine Clique bzw. stabile Menge ist. Gibt es in G keine Clique bzw. stabile Menge, die mehr Elemente als U enthält, so nennt man U größte Clique bzw. größte stabile Menge. Die Anzahl Elemente einer größten Clique bzw. stabilen Menge nennt man Cliquenzahl bzw. Stabilitäts- oder Unabhängigkeitszahl. Die Anzahl Knoten einer kleinsten Knotenüberdeckung von G nennt man Knotenüberdeckungszahl von G. Statt über Teilmengen von V definiert man Cliquen oder stabile Mengen auch als spezielle Teilgraphen. Als Cliquenüberdeckung von G der Größe k bezeichnet man eine Partition der Knotenmenge V(G) in k paarweise disjunkte Cliquen V₁,V₂,...,V_k. Gerichtete Graphen oder solche mit Mehrfachkanten sind nicht Gegenstand derartiger Betrachtungen, da es nicht auf die Richtung oder Vielfachheit der Kanten ankommt.

Probleme und Komplexität

Das Entscheidungsproblem zu einem Graphen G und einer natürlichen Zahl k zu entscheiden, ob G eine Clique der Größe k enthält, wird Cliquenproblem genannt. Das zugehörige Optimierungsproblem fragt nach der Cliquenzahl eines Graphen. Das zugehörige Suchproblem fragt nach einer größten Clique. Analog ist das Stabilitätsproblem über stabile Mengen definiert und das Knotenüberdeckungsproblem durch Knotenüberdeckungen. Alle drei Probleme sind NP-vollständig. Die zugehörigen Optimierungs und Suchprobleme sind NP-Äquivalent. Die NP-Schwere des Stabilitätsproblems lässt sich dabei leicht durch Reduktion auf das Cliquenproblem zeigen, indem man den Komplementgraphen bildet. Die NP-Schwere des Knotenüberdeckungsproblems folgt aus dem Satz, dass die Stabilitätszahl eines Graphen immer der Anzahl Knoten eines Graphen abzüglich seiner Knotenüberdeckungszahl entspricht, denn das Komplement einer kleinsten Knotenüberdeckung ist immer eine größte stabile Menge und umgekehrt. Für den Nachweis der NP-Schwere des Cliquenproblems existiert eine Reduktion auf 3-SAT. König konnte jedoch schon 1931 zeigen, dass in bipartiten Graphen die Knotenüberdeckungszahl der Paarungszahl entspricht. Für das Problem eine größte Paarung zu finden, gibt es aber einen polynomiellen Algorithmus. In bipartiten Graphen lässt sich daher auch eine kleinste Knotenüberdeckung und eine größte stabile Menge in polynomieller Zeit berechnen. Eine größte Clique lässt sich entsprechend der obigen Reduktion in polynomieller Zeit berechnen, wenn der Komplementgraph bipartit ist. Tatsächlich gilt sogar etwas stärker, dass Cliquenzahl, Stabilitätszahl und Knotenüberdeckungszahl in perfekten Graphen in polynomieller Zeit berechnet werden können. Da die Farbzahl und die Cliquenzahl in solchen Graphen identisch sind, ist auch ihre Farbzahl in polynomieller Zeit berechenbar. Kategorie:Graphentheorie Kategorie:Übersichtsartikel zur Graphentheorie Kategorie:Komplexitätstheorie ja:最大クリーク問題

Ungerichteter Graph

Glossar Graphentheorie#Ungerichteter Graph

Teilmenge

Die Mengenlehre ist ein grundlegendes Teilgebiet der Mathematik. Zahlreiche Disziplinen wie Algebra, Analysis, Maßtheorie, Stochastik oder Topologie werden auf der Mengenlehre aufgebaut. Darüber hinaus gibt es wichtige Verbindungen zur Prädikatenlogik.

Geschichte

Naive Mengenlehre

Die Mengenlehre geht zurück auf Georg Cantor. Nach seiner Definition von 1877 ist eine Menge "eine Zusammenfassung von bestimmten wohl unterschiedenen Objekten der Anschauung oder des Denkens, welche die Elemente der Menge genannt werden, zu einem Ganzen". Die Mengenlehre auf der Grundlage dieser Definition wurde später als naive Mengenlehre bezeichnet. Sie führt zu Widersprüchen, insbesondere dann, wenn Mengen eingeführt werden, die sich selbst als Element enthalten. Am bekanntesten ist die Russellsche Antinomie.

Typentheorie

Zur Vermeidung dieser Widersprüche hat Russell selbst einen stufenweisen Aufbau der Mengenlehre vorgeschlagen und hierfür 1903, zusammen mit Whitehead die Typentheorie entwickelt. Danach hat eine Menge stets einen höheren Typ als ihre Elemente. Aussagen wie "diese Menge enthält sich selbst als Element" lassen sich in dieser Theorie gar nicht formulieren. Die Typentheorie wurde später zu einer axiomatischen Theorie ausgebaut. Sie lässt sich als widerspruchsfrei nachweisen. Ihre sprachlichen Mittel sind jedoch nicht stark genug, um die gesamte Mathematik darauf aufzubauen.

Typenfreie axiomatische Mengenlehre

Andere Versuche, die Mengenlehre axiomatisch aufzubauen, greifen auf eine typenfreie Prädikatenlogik zurück. Grundbegriffe sind hier nur noch
- eine einzige Art von Objekten und
- die Elementbeziehung zwischen diesen. Das bekannteste System dieser Art ist die Zermelo-Fraenkel-Mengenlehre, deren Grundlagen 1908 von E. Zermelo gelegt wurden. Die endgültige Fassung erfolgte 1922 aufgrund einer Arbeit von A. Fraenkel. Dieses System wird oft als "ZF" zitiert. Noch von Zermelo wurde das - nicht ganz unumstrittene - Auswahlaxiom hinzugefügt. In dieser Form wird es als "ZFC" (C für choice - englisch: Auswahl) bezeichnet. Die überwiegende Mehrheit der Mathematiker betrachtet heute ZFC als eine geeignete Grundlage für die moderne Mathematik. Die einzige Grundrelation in ZF oder ZFC ist

\in

(gesprochen: Element von), z.B. x

\in

M, wenn x als Element in M enthalten ist. Die Existenz von "Urelementen", die keine Mengen sind, wird in dieser Theorie nicht postuliert. Die Axiome sind so formuliert, dass die bekannten Widersprüche der Cantorschen Mengenlehre vermieden werden. Wichtig sind hier vor allem das Fundierungsaxiom und das Aussonderungsaxiom, die es unmöglich machen, die Russellsche Antinomie zu formulieren. Einen Beweis für die Widerspruchsfreiheit der Zermelo-Fraenkel-Mengenlehre gibt es jedoch nicht. Im Rahmen einer Mathematik, die auf der Zermelo-Fraenkel-Mengenlehre basiert, lässt sich ein solcher Beweis auch grundsätzlich nicht führen (Gödelscher Unvollständigkeitssatz).

Präzisierung der Cantorschen Mengenlehre

Auch Mathematiker, die nicht auf eine Axiomatisierung der Mengenlehre aufbauen wollten, mussten dafür sorgen, dass die bekannten Widersprüche ausgeschlossen werden. Als Beispiel sollen hier die Definitionen von Erich Kamke dargestellt werden, dessen "Mengenlehre" seit 1928 in zahlreichen Auflagen erschienen ist und als eine Standard-Einführung angesehen werden kann: Kamke zitiert die Cantorsche Definition und erläutert dann: :(a) "Es sei

\mathfrak

eine wohldefinierte Eigenschaft(…), die mindestens einem 'Ding' zukommt oder eine Aussage, die für mindestens ein Ding wahr ist…"; :: An späterer Stelle führt Kamke dazu aus: "Damit ist der Mengenbegriff auf einen Begriff ähnlicher Allgemeinheit zurückgeführt, dessen genaue Festlegung keineswegs einfacher ist(…) Jedenfalls gibt es Eigenschaften, die nach übereinstimmender Meinung eine Menge einwandfrei festlegen, z.B. die Menge der natürlichen Zahlen(…). Wir wollen immer annehmen, dass von solchen einwandfreien Mengen ausgegangen wird." - Das Kamke-Zitat geht dann weiter: :"(…)ferner sei die Gesamtheit der 'Dinge' m mit der Eigenschaft

\mathfrak

eine wohlbestimmte Gesamtheit(…)" :: Dazu gibt er die Anmerkung: "Ob das zutrifft, ist mit der auch sonst in der Mathematik üblichen Sorgfalt zu untersuchen", und fährt dann fort: :(b) "Durch den Akt der Definition wird die Gesamtheit der 'Dinge' m mit der Eigenschaft

\mathfrak

als ein neues 'Ding' eingeführt und 'Menge' M oder M(m) genannt;(…) Als Konsequenz hieraus ergibt sich laut Kamke: :"Da durch die Bildung einer Menge ein neues Ding, ein neuer Begriff geschaffen werden soll(…), ist die Menge als verschieden vom jedem ihrer Elemente anzusehen(…) Hiernach sind folgende 'Mengen' sinnlos, da in sich selbst widerspruchsvoll: :(α) jede Menge, die sich selbst als Element enthält; :(β) die Menge aller Mengen, da sie sich selbst als Element enthalten müsste; :(γ) Die Menge aller Mengen, die sich nicht als Element enthalten (Russell), da sie nach dem Vorangehenden nichts als die in (β) genannte Menge ist." Hier wird also ansatzweise ein hierarchischer Mengenbegriff verwendet (ähnlich wie in der Typentheorie). Die Rechtfertigung seiner Vorgehensweise sieht Kamke darin, dass für "ernste unlösbare Widersprüche (…) irgendwelche Anzeichen" nicht vorliegen. Allerdings hat eine solche Einschränkung des Mengenbegriffs zur Folge, dass es nun durchaus "bestimmte wohlunterschiedene Objekte (…) unseres Denkens" gibt, die sich auch begrifflich "zu einem Ganzen" zusammenfassen lassen, ohne dass wir dieses Ganze als "Menge" bezeichnen dürften. (Die Gesamtheit aller Mengen ist ein Beispiel, die Gesamtheit der Kardinalzahlen ein anderes). Das ist ganz gegen Cantors Intention. Wenn solche "Un-Mengen" mit einbezogen werden sollen, wird zuweilen der Begriff Klasse verwendet.

Rückwirkungen auf die Mathematik als Wissenschaft. Bourbaki

Cantors Konzept wurde von den Mathematikern des späten 19. Jahrhunderts keineswegs als revolutionär angesehen. Der Ruf der Logik als mathematischer Disziplin war schlecht. Verallgemeinerungen auf diesem Niveau galten als überflüssig und, als dabei gar noch Antinomien auftraten, als lästig. Poincaré spottete: "Die Logik ist gar nicht mehr steril - sie zeugt jetzt Widersprüche." Im Verlauf des ersten Drittels des 20. Jahrhunderts setzte sich dann, zunächst hauptsächlich bei jungen Mathematikern, die Ansicht durch, dass Mengenlehre eine entscheidend wichtige Grundlage für die Strukturierung der Mathematik sei. Paradoxerweise erfolgte diese Aufwertung parallel zu der Erkenntnis, dass die aufgetretenen Probleme grundsätzlicher Natur und prinzipiell unlösbar sind (Gödelscher Unvollständigkeitssatz). Was von den Spezialisten als Grundlagenkrise der Mathematik begriffen wurde, wurde von der Mehrheit der Mathematik Schaffenden kaum beachtet. Kennzeichnend für diese Auffassung ist das Unternehmen einer Gruppe von Mathematikern, die unter dem Pseudonym Bourbaki die gesamte Mathematik auf der Grundlage der Mengenlehre einheitlich neu darstellen wollte. Die Entscheidung zwischen den möglichen Grundlegungen fiel pragmatisch aus: Zermelos typenfreies Axiomensystem schien damals leichter zu handhaben als Russells Typentheorie. Jenes wird heute ganz überwiegend als Grundlage der Mathematik betrachtet.

Rückwirkungen auf die Schulmathematik. "Neue Mathematik"

Gegen Ende der 1960er Jahre wurden Grundbegriffe der Mengenlehre in den Schulunterricht eingeführt. Insbesondere in den Eingangsklassen der Grundschulen fand eine grundlegende Veränderung des Rechenunterrichts statt, der von nun an als Mathematikunterricht aufgefasst wurde. Die zum Teil sicher überzogene Betonung des Mengenbegriffs wurde bald wieder zurückgenommen.

Kategorientheorie

Eine alternative Mengentheorie kann man aufbauend auf der Kategorientheorie mit Hilfe von Topoi definieren.

Mengenlehre und Informatik

Als Grundlage der Informatik reicht die typenfreie Mengenlehre nach Zermelo und Fraenkel allein nicht aus, da sie hochgradig unkonstruktiv ist, also den Begriff des Algorithmus kaum erfasst. Aus diesem Grunde wurden seit den 1970er Jahren konstruktive Kalküle entwickelt, die Klassifizierungskonzepte wie Datentypen usw. beinhalten. Es wird behauptet, dass diese Theorien im Hinblick auf Universalität und Anwendungsbereich der klassischen Mengentheorie gleichkommen.

Die Überarbeitung des geschichtlichen Teils ist (von sprachlichen Korrekturen abgesehen) jetzt abgeschlossen. Der folgende Teil des Artikels wird nun gründlich überarbeitet und ist derzeit noch im Rohbau.

Definitionen

Gleichheit

Zwei Mengen heißen gleich, wenn sie die selben Elemente enthalten. Diese Definition bezeichnet die Extensionalität und damit die grundlegende Eigenschaft von Mengen. Formal: :::

A=B \iff \forall x \left(x \in A \,\leftrightarrow x \in B \right)

Tatsächlich muss eine Menge A aber meist intensional beschrieben werden. Das heißt: Es wird eine Aussageform P(x) angegeben (mit einer Objektvariablen x, die eine wohlbestimmte Definitionsmenge D haben sollte), sodass x ∈ A genau dann gilt, wenn P(x) zutrifft. Dafür schreibt man dann: :::

A = \

Zu jeder Menge A gibt es viele verschiedene Aussageformen P(x), die diese beschreiben. Die Frage, ob zwei gegebene Aussageformen P(x) und Q(x) die selbe Menge beschreiben, ist keineswegs trivial. Im Gegenteil: Viele Fragestellungen der Mathematik lassen sich dieser Form formulieren: "Sind

\

und

\

die gleiche Menge?".

Leere Menge

Die Menge, die kein Element enthält, heißt leere Menge. Sie wird mit

\varnothing

oder auch

\

bezeichnet. Aus der Extensionalität der Mengen folgt, dass es nur eine leere Menge gibt: Jede "andere" leere Menge enthält die selben Elemente (nämlich keine), ist also gleich

Teilmenge

Eine Menge A heißt Teilmenge einer Menge B, wenn jedes Element von A auch Element von B ist. B wird dann zuweilen auch Obermenge von A genannt. Formal: :

\subseteq  :\Longleftrightarrow \forall x  \left(  \in A \rightarrow x \in B \right)

.
- Echte Teilmenge: A ist echte Teilmenge von B (oder B ist echte Obermenge von A), wenn A Teilmenge von B ist, aber von B verschieden. Die Relation "ist Teilmenge von" bildet eine Halbordnung. Die Relation "echte Teilmenge" ist eine strenge Halbordnung. Es gibt zwei Notationen:
-

\subseteq

für "Teilmenge" und

\subset

für "echte Teilmenge" oder
-

\subset

für "Teilmenge" und

A \subsetneq B

für "echte Teilmenge". In diesem Artikel wird das erstgenannte System verwendet, es sind jedoch beide weit verbreitet.

Schnittmenge

Halbordnung Gegeben ist eine Menge U von Mengen. Die Schnittmenge von U ist die Menge der Elemente, die in jedem Element von U enthalten sind. Formal: :::

\bigcap U := \

. Ist U eine Paarmenge, also

U\,=\

, so schreibt man für

\bigcap U

gewöhnlich :::

\cap := \

und liest dies: A geschnitten mit B (oder: Der Durchschnitt von A und B) ist die Menge aller Elemente, die sowohl in A als auch in B enthalten sind. Diese Schreibweise lässt sich leicht auf den Durchschnitt aus endlich vielen Mengen

verallgemeinern. Abweichende Schreibweise für den Durchschnitt aus beliebig vielen Mengen: Die Elemente der Menge

U

, die ja selbst wieder Mengen sind, werden mit

A_\lambda

bezeichnet. Es wird eine "Indexmenge"

\Lambda

eingeführt, sodass

U = \

ist. Die Schnittmenge

\bigcap U

wird dann geschrieben als: :::

\bigcap_ A_\lambda := \

, also die Menge aller Elemente, die in sämtlichen Mengen

A_\lambda

enthalten sind.

Vereinigungsmenge

Dies ist der zu Schnittmenge duale Begriff: Die Vereinigungsmenge von U ist die Menge der Elemente, die in mindestens einem Element von U enthalten sind. Formal: :::

\bigcup U := \

. Für

U\,=\

schreibt man wieder :::

\cup := \

und liest dies: A vereinigt mit B (oder: Die Vereinigung von A und B) ist die Menge aller Elemente, die in A oder in B enthalten sind. Das "oder" ist hier nicht-ausschließend zu verstehen. Die Vereinigung umfasst auch die Elemente, die in beiden Mengen enthalten sind. Auch diese Schreibweise ist für die Vereinigung endlich vieler Mengen geeignet. Unter Verwendung der Indexmenge

\Lambda

schreibt man: :::

\bigcup_ A_\lambda := \

Differenz und Komplement

duale
- Komplement:

\complement:=\

bezeichnet das Komplement von

A

\mathbb

, das ist die Menge aller Elemente von

\mathbb

, die nicht in A liegen.

- Differenzmenge:

\setminus  = \

(A ohne B) ist die Menge aller Elemente, die in A enthalten sind, aber nicht in B
- symmetrische Differenz:

\, \triangle \,  := \left( A \setminus B \right) \cup \left( B \setminus A \right)

ist die Menge aller Elemente, die in einer aber nicht in beiden der gegebenen Mengen liegen
- Mächtigkeit:

\left| A \right|

bezeichnet die Mächtigkeit (auch Kardinalität) der Menge

A

, also die Anzahl der Elemente von

A

. Für eine endliche Menge ist die Mächtigkeit eine natürliche Zahl; bei unendlichen Mengen unterscheidet man nach verschiedenen Graden der Unendlichkeit. Diese werden als Kardinalzahlen bezeichnet.
- Potenzmenge: Die Potenzmenge

\mathcal \left(  \right)

ist die Menge aller Teilmengen von

.
- Produktmenge oder kartesisches Produkt
- Die zweistellige Produktmenge

A\times B := \

ist die Menge aller geordneten Paare, die sich aus den Mengen

A

und

B

bilden lassen.
- Die Produktmenge beliebig vieler Mengen

\prod_ A_\lambda := \

ist die Menge aller Abbildungen, die einem Indexelement

\lambda

ein Element der Menge

A_\lambda

zuordnen.

Anmerkungen

- Für die Bezeichnung des Komplements einer Menge

A

gibt es einige Varianten: Es wird gelegentlich auch durch

\overline

A^C

oder

A^'

symbolisiert.
- Die Potenzmenge einer Menge

A

wird mitunter auch mit

2^A

bezeichnet. Diese Notation ist durch die Eigenschaft

|\mathcal(A)| = 2^

einer endlichen Menge A motiviert, welche unter Einbeziehung der Arithmetik der Kardinalzahlen dann auch für beliebige unendliche Mengen gilt.
-

\in

\subset

und

\subseteq

sind Relationen. Die Negation dieser Relationen kann durch das durchgestrichene jeweilige Relationssymbol bezeichnet werden, also zum Beispiel durch

\notin

. Außerdem ist es möglich, die Reihenfolge der beiden Argumente zu vertauschen, wenn dabei auch das Relationssymbol umgedreht wird. So kann also anstelle von

x\in A

auch

A\ni x

, anstelle von

A\subseteq B

auch

B\supseteq A

und anstelle von

A\subset B

auch

B\supset A

geschrieben werden. Auch ein gleichzeitiges Durchstreichen und Umdrehen dieser Relationssymbole ist denkbar.
- Die leere Menge kann – wie jede andere Menge auch – Element einer Menge sein: Die beiden Mengen

\varnothing

und

\

sind verschieden.
- Die leere Menge ist Teilmenge jeder beliebigen Menge. Deshalb tritt sie als Element jeder Potenzmenge auf; jede Potenzmenge umfasst mindestens dieses eine Element.
- Für eine endliche, nicht leere Indexmenge

\Lambda = \

gilt

\bigcap_ A_\lambda = A_ \cap A_ \cap \cdots \cap A_

und

\bigcup_ A_\lambda = A_ \cup A_ \cup \cdots \cup A_

. Die Definitionen für den zweistelligen Fall und den Fall beliebig vieler Mengen sind also zueinander konsistent.
- Es gilt

\bigcap_ A_\lambda = \bigcap\

und

\bigcup_ A_\lambda = \bigcup\

.
- Für den leeren Schnitt liefert die Definition

\bigcap_ A_\lambda = \bigcap\varnothing = \mathbb

, für die leere Vereinigung

\bigcup_ A_\lambda = \bigcup\varnothing = \varnothing

und für die leere Produktmenge

\prod_ A_\lambda = \varnothing

- Die Mengen

\left(A_\times A_\right) \times A_

und

A_\times \left( A_ \times A_ \right)

sind nicht gleich, aber durch die Bijektion

((a,b),c)\mapsto(a,(b,c))

zueinander isomorph. In der Regel wird deshalb nicht zwischen diesen beiden Mengen unterschieden. Diese Assoziativität bis auf Isomorphie erlaubt es, beliebige Produktengen aus einer endlichen Anzahl

n

von Mengen

A_: i\in\mathbb,1\leq i\leq n

mit der Menge der n-Tupel zu identifizieren und ohne Rücksicht auf die konkrete Klammerung mit

A_\times A_\times \cdots \times A_

zu bezeichnen.
- Für das Mengenprodukt aus identischen Faktoren gibt es abkürzende Schreibweisen:
- Anstelle des n-fachen endlichen Mengenprodukts

A\times A\times\cdots\times A

schreibt man auch

A^n

.
- Das unendliche Mengenprodukt

\prod_ A

ist kanonisch isomorph zur Menge aller Abbildungen

\Lambda\rightarrow A

. In Analogie zum endlichen Fall wird dafür die Schreibweise

A^\Lambda

benutzt.
- Die Mengen

A_\times A_

und

\prod_A_\lambda

sind nicht gleich, aber durch die Bijektion

(a,b)\mapsto f_

mit

f_:\\to \mathbb

\lambda_1\mapsto a

\lambda_2\mapsto b

zueinander isomorph. Die Definition der zweistelligen Produktmenge ist also mit der Definition der Produktmenge beliebig vieler Mengen konsistent, weshalb für eine endliche nichtleere Produktmenge

\Lambda = \

in der Regel auch nicht zwischen

\prod_ A_\lambda

und

A_\times A_\times \cdots \times A_

unterschieden wird.

Beispiele

Wir betrachten die Mengen

\mathbb = \

A = \

und

B = \

. Es gelten:
-

2\in A

2\notin B

A\subseteq\mathbb

B\subseteq\mathbb

\mathbb\subseteq\mathbb

A\subset\mathbb

B\subset\mathbb

A\cap B = \

A\cup B = \mathbb

\complement = \

\complement = \

\complement=\varnothing

\complement=\mathbb

A\setminus B = \

B\setminus A = \

\mathbb\setminus A = \

A\setminus\mathbb = \varnothing

A\triangle B = \

A\triangle\mathbb = \

B\triangle\mathbb = \

\left| \mathbb\right|

= 3,

\left| A\right|

= 2,

\left|\varnothing\right|

= 0,

\left|\\right|

= 1
-

\mathcal \left(A\right) = \

\mathcal \left(\mathbb\right) = \

A\times B = \

A\times\ = \

A^2 = \

\^3 = \

\varnothing\notin\varnothing

\varnothing\in\

\mathcal \left(\varnothing\right) = \

\mathcal \left(\\right) = \

A\times\varnothing = \varnothing\times A = \varnothing

\mathbb^+\subset \mathbb \subset \mathbb \subset \mathbb \subset \mathbb \subset \mathbb

Gesetzmäßigkeiten

Die Menge

\mathcal\left(\mathbb\right)

ist bezüglich der Relation

\subseteq

partiell geordnet, denn für alle

A,B,C\subseteq\mathbb

gilt:
- Reflexivität:

A\subseteq A

- Antisymmetrie: Aus

A\subseteq B

und

B\subseteq A

folgt

A = B

- Transitivität: Aus

A\subseteq B

und

B\subseteq C

folgt

A\subseteq C

Die Mengen-Operationen Schnitt

\cap

und Vereinigung

\cup

sind zueinander kommutativ, assoziativ und distributiv:
- Kommutativgesetz:

A \cup B = B \cup A

A \cap B = B \cap A

- Assoziativgesetz:

\left( A \cup B \right) \cup C = A \cup \left( B \cup C \right)

\left( A \cap B \right) \cap C = A \cap \left( B \cap C \right)

- Distributivgesetz:

A \cup \left( B \cap C \right) = \left( A \cup B \right) \cap \left( A \cup C \right)

A \cap \left( B \cup C \right) = \left( A \cap B \right) \cup \left( A \cap C \right)

- De Morgansche Gesetze:

\complement( A \cup B) = \complement \cap \complement

\complement = \complement \cup \complement

Für die Differenzmenge gelten folgende Gesetzmäßigkeiten:
- Distributivgesetze:

(A \cap B) \setminus C = (A \setminus C) \cap (B \setminus C)

(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)

A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)

und

A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)

- Assoziativgesetze:

(A \setminus B) \setminus C = A \setminus (B \cup C)

und

A \setminus (B \setminus C) = (A \setminus B) \cup (A \cap C)

Für die symmetrische Differenz gelten folgende Gesetzmäßigkeiten:
- Kommutativgesetz:

A \triangle B = B \triangle A

- Assoziativgesetz:

(A \triangle B) \triangle C = A \triangle (B \triangle C)

- Distributivgesetz:

(A \triangle B) \cap C = (A \cap C) \triangle (B \cap C)

A \triangle \varnothing = A \quad A \triangle A = \varnothing

Die Algebra der Mengen ist eine so genannte Boolesche Algebra.

Siehe auch

- Tabelle mathematischer Symbole
- Universum (Mathematik)

Weblinks

- [http://www.math.niu.edu/~rusin/known-math/index/03EXX.html Mathematical Atlas Artikel]
- [http://planetmath.org/encyclopedia/SetTheory.html PlanetMath Artikel]
- [http://www.mathe-online.at/mathint/mengen/i.html Mathe Online]
- http://plaz.upb.de/lehrerbildung/plan/plan.php?id=sw0306 ja:集合論

Kante (Graphentheorie)

Glossar Graphentheorie#Kante

Independent Set

Independent Set ist ein Begriff der theoretischen Informatik aus dem Bereich der Graphentheorie. Man bezeichnet damit eine Menge von Knoten, deren Elemente untereinander nicht verbunden sind.

Formale Definition und Eigenschaften

Im Folgenden sei

G := (V, E)

ein Graph im Sinne der Graphentheorie mit Knotenmenge

V

und Relation

E \sube V \times V

. Ferner sei

V^\prime \sube V

eine Menge von Knoten.

Definition

V^\prime

ist Independent Set von

G \Longleftrightarrow \forall u,v \in V^\prime: u \not= v \Rightarrow \left( u,v \right) \notin E

Eigenschaften

Die folgenden Aussagen sind äquivalent:
-

V^\prime

ist Independent Set von

G

V \setminus

ist Vertex Cover von

G

\forall V^ \sub V^\prime : V^

ist Independent Set von

G

V^\prime

ist Clique in

\left( V,E ^ \prime \right)

, mit

E ^ \prime := \left( V \times V \right) \backslash E

Entscheidungsproblem

INDEPENDENT SET ist ein NP-vollständiges Entscheidungsproblem. Zu entscheiden ist, ob in einem gegebenen Graph ein Independent Set einer gegebenen Mindestgröße existiert. Gegeben sei eine Instanz

I := (G, K)

mit

K \in \N

, wobei

G := (V, E)

einen Graph im Sinne der Graphentheorie mit der Knotenmenge

V

und der Relation

E \sube V \times V

darstellt. Existiert eine Menge

V^\prime \sube V

mit

\left| V' \right| = K

, für die gilt:

\forall u,v \in V^\prime: u \not= v \Rightarrow \left( u,v \right) \notin E

Optimierungsproblem

Bei dem Optimierungsproblem MAXIMUM INDEPENDENT SET wird zu einem gegebenen Graph ein Independent Set maximaler Größe gesucht. Kategorie:Graphentheorie Kategorie:Komplexitätstheorie

Teilgraph

Bei der Untersuchung von Grapheneigenschaften schließt man häufiger von lokalen auf globale Eigenschaften von Graphen und umgekehrt. Um derartige Vorgänge besser beschreiben zu können, definiert man geeignete Relationen zwischen Graphen und lokalen Gebieten innerhalb dieser Graphen. Besonders wichtig sind dabei Teilgraphenbeziehungen. Die Begriffe Teilgraph und Untergraph sind Spezialfaelle der entsprechenden allgemeineren Begriffe Teil-Struktur und Unter-Struktur aus der Modelltheorie. Eine Unter-Struktur ist anschaulich gesehen ein Ausschnitt aus einer Struktur, bei der alle Beziehungen zwischen den Elementen (bzw. Knoten) erhalten bleiben. Beispiel siehe unten: G2, G3 sind Untergraphen von G aber G1 ist kein Untergraph sondern nur ein Teilgraph von G. In Teil-Strukturen können also zusätzlich noch Beziehungen zwischen den Elementen wegfallen. Jede Unter-Struktur ist eine Teil-Struktur aber nicht umgekehrt. Im folgenden werden beide Begriffe für Graphen näher definiert.

Definitionen

Teilgraph

G₁=(V₁,E₁) heißt Teilgraph oder Subgraph von G₂=(V₂,E₂), falls V₁ Teilmenge von V₂, also

V_1\subseteq V_2

und
- in Graphen ohne Mehrfachkanten E₁ Teilmenge von E₂ ist,

E_1\subseteq E_2

,
- in ungerichteten Graphen mit Mehrfachkanten

E_1(v)\subseteq E_2(v)

für alle zweielementigen Teilmengen v von V₂, also

v:=

, gilt, wobei

E_(v)

die Menge der Kanten zwischen den Knoten aus v ist,
- in gerichteten Graphen mit Mehrfachkanten

E_1(v)\subseteq E_2(v)

für alle Teilmengen v aus dem kartesischen Produkt V₂xV₂ gilt. Umgekehrt heißt G₂ Supergraph oder Obergraph von G₁. Bei einem knotengewichteten bzw. kantengewichteten Graph G₂ wird von einem Teilgraph G₁ zudem verlangt, dass die Gewichtsfunktion g₁ von G₁ kompatibel zu der Gewichtsfunktion g₂ von G₂ ist, d.h. für jeden Knoten v bzw. für jede Kante e von G₂ gilt

g_1(v) = g_2(v) \mbox g_1(e) = g2(e)

Untergraph bzw. Induzierter Teilgraph

Gilt zusätzlich:
- in Graphen ohne Mehrfachkanten,

E_1 = E_2 \cap

, d.h. G₁ enthält alle Kanten zwischen den Knoten in V₁, die auch in G₂ vorhanden sind.
- in ungerichteten Graphen mit Mehrfachkanten,

E_1(v) = E_2(v) \cap

für alle zweielementigen Teilmengen v von V₂,
- in gerichteten Graphen mit Mehrfachkanten,

E_1(v) = E_2(v) \cap

für alle v aus dem kartesischen Produkt V₂xV₂, so bezeichnet man G₁ auch als den durch V₁ induzierten Teilgraph von G₂ und notiert diesen auch mit G₂[V₁] Bemerkungen:
- Induzierte Teilgraphen sind immer eindeutig durch die entsprechende Knotenmenge festgelegt.
- Besonders wichtige Teilgraphen entstehen durch das Weglassen von Knoten bzw. Kanten. Sei der Graph G(V,E) gegeben, dann bezeichnet

G\setminus A, A \subseteq V

den Graphen, der durch Weglassen der Knoten aus A und aller mit diesen Knoten inzidenten Kanten entsteht. Die so entstehenden Teilgraphen sind immer induzierte Teilgraphen!

Beispiele

In der folgenden Abbildung sind die Graphen G₁, G₂, G₃ Teilgraphen von G, wobei aber nur G₂ und G₃ induzierte Teilgraphen sind. G₃ entsteht dabei aus G durch Weglassen der Knoten 1,3,7 und ihrer inzidenten Kanten. bild:Forbys_teilgraph_example.png

Minor

Ein Graph G₁ wird Minor des Graphen G₂ genannt, falls G₁ isomorph zu einem durch Knotenverschmelzung entstandenen Untergraph von G₂ ist. Knotenverschmelzung bedeutet hier, dass zwei adjazente (benachbarte) Knoten V₁ und V₂ unter Entfernung einer zu diesen beiden Knoten inzidenten Kante zu einem Knoten V₁₂ „verschmolzen“ werden, wobei alle restlichen Kanten beibehalten werden. Zum Beispiel ist in der folgenden Abbildung G1 ein Minor von G2. bild:Forbys_graphs_minor-relation2.png Die Minor-Beziehung definiert eine partielle Ordnungsrelation auf den Isomorphie-Klassen von Graphen. Robertson und Seymour haben gezeigt, dass für jede unendliche Folge G₁,G₂,... von endlichen Graphen stets Indizes i und j mit i < j existieren, so dass G_i ein Minor von G_j ist. Siehe auch: Satz von Kuratowski, Satz von Robertson und Seymour Kategorie:Graphentheorie Kategorie:Übersichtsartikel zur Graphentheorie

Gerichteter Graph

Als gerichteten Graph (oft auch kurz Digraph, von englisch directed graph) bezeichnet man in der Graphentheorie einen Graph, der gerichtete Kanten enthalten kann. gerichtete Kanten Darstellung eines gerichteten Graphen Gerichtete Graphen können azyklisch oder zyklisch sein. Azyklische Graphen kann man topologisch sortieren. Sie können zusammenhängend oder unzusammenhängend sein. Darüber hinaus können sie endlich oder unendlich viele Knoten besitzen. topologisch sortieren topologisch sortieren topologisch sortieren
Zyklische Graphen Weitere Informationen findet man im Artikel Typen von Graphen in der Graphentheorie. Kategorie:Graphentheorie

Entscheidungsproblem

Als Entscheidungsproblem bezeichnet man heute in der Theoretischen Informatik allgemein Probleme, für die zu einer gegebenen Eingabe als Lösung nur zwei Antworten (z. B. ja oder nein bzw. 1 oder 0 usw.) vorgesehen sind. Jedes derartige Problem lässt sich auch als das Wortproblem einer formalen Sprache auffassen. Deshalb wird auch häufig der Begriff (formale) Sprache anstelle von Entscheidungsproblem verwendet. Ursprünglich galt als Entscheidungsproblem die Frage, ob es einen Algorithmus gibt, der für einen beliebigen Ausdruck in der Prädikatenlogik bestimmt, ob es sich um eine allgemeingültige Aussage handelt oder nicht. Dieses (spezielle) Entscheidungsproblem wurde 1928 von David Hilbert gestellt (siehe Hilbertprogramm). Alan Turing und Alonzo Church haben für das Problem 1936 festgestellt, dass es unlösbar ist (siehe Halteproblem). Eine formale Sprache

\mathbf

ist entscheidbar (rekursiv entscheidbar), wenn ihre charakteristische Funktion berechenbar ist. Es gibt dann also eine berechenbare Funktion

\mathbf

, sodass für alle Worte

\mathbf

über die Symbole der Sprache

\mathbf

gilt:

f(w)=\begin 1, & w \in S\\ 0, & w \notin S\end

Die Semi-entscheidbarkeit (Rekursive Aufzählbarkeit) einer (formalen) Sprache

\mathbf

ist dadurch gekennzeichnet, dass ihre partielle (eingeschränkte) charakteristische Funktion berechenbar ist. Es gibt dann folglich eine berechenbare Funktion

\mathbf

, sodass für alle Worte

\mathbf

über die Symbole der Sprache

\mathbf

gilt:

f^(w)=\begin 1, & w \in S\\ , & w \notin S\end

Siehe auch

- Berechenbarkeit
- Äquivalenzproblem
- Endlichkeitsproblem
- Leerheitsproblem
- Optimierungsproblem
- Suchproblem
- Turingmaschine
- Akzeptieren Kategorie:Theoretische Informatik Kategorie:Rekursionstheorie Kategorie:Formale Sprachen Kategorie:Wortexport

Suchproblem

Als Suchproblem bezeichnet man in der Theoretischen Informatik ein Problem, bei dem zu einer gegebenen Eingabe eine bestmögliche Lösung gesucht ist. Das Suchproblem unterscheidet sich vom zugehörigen Optimierungsproblem darin, dass beim Optimierungsproblem nicht die Lösung selbst, sondern der ihr zugeordnete Zahlwert gesucht ist. Formal ist ein Suchproblem definiert durch einen in einer symbolischer Repräsentation dargelegeten Start- und Zielzustandsbeschreibung, einer Menge von Operatoren und einer Funktion, welche bestimmt, ob der aktuelle Zustand ein Zielzustand ist. Die Anwendung aller vorhandenen Operatoren auf den Startzustand und auf die so resultierenden Zustände spannen den Suchraum auf, welcher häufig auch als Suchbaum notiert werden kann.

Siehe auch

- Entscheidungsproblem
- Suche
- künstliche Intelligenz Kategorie:Theoretische_Informatik

NP-Vollständigkeit

Der Begriff NP-Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der Theoretischen Informatik, der im Jahre 1971 von Stephen A. Cook durch den Satz von Cook eingeführt wurde; er zeichnet spezielle formale Sprachen der Komplexitätsklasse NP aus. So werden solche Sprachen NP-vollständig genannt, die -- intuitiv gesprochen -- die vollständige Schwierigkeit aller Sprachen aus NP in sich tragen. Insbesondere haben NP-vollständige Sprachen folgende Eigenschaften: # Es konnte bisher für kein Entscheidungsverfahren nachgewiesen werden, dass es in polynomieller Zeit eine korrekte Antwort liefert. # Wenn für eine NP-vollständige Sprache ein Verfahren gefunden wird, das in polynomieller Zeit eine korrekte Antwort liefert, dann können alle Probleme in NP in polynomieller Zeit entschieden werden.

Definition

Ein Problem (genauer: ein Entscheidungsproblem) L heißt NP-vollständig genau dann, wenn:
- L in der Klasse NP liegt, das heißt L∈NP und
- L ist NP-schwer, das heißt, jedes Problem in NP kann durch eine Polynomialzeitreduktion auf L reduziert werden.

Nachweis der NP-Vollständigkeit

Der Nachweis der ersten Eigenschaft für ein Problem ist in aller Regel leicht. Man "rät" eine Lösung und zeigt, dass man in Polynomialzeit verifizieren kann, ob die Lösung wirklich zutrifft. Der Nachweis der zweiten Eigenschaft, die man für sich allein mit NP-Schwer (oder oft - eigentlich falsch - aus dem englischen zurückübersetzt mit NP-Hart) bezeichnet, ist schwieriger. Insbesondere bereitet es Probleme, eine Aussage für beliebige Probleme in NP zu zeigen. Daher nimmt man gewöhnlich ein ähnliches Problem, für das die NP-Vollständigkeit schon bekannt ist und reduziert es auf dasjenige Problem, für das man die Eigenschaft der NP-Schwere zeigen will. Aus der Transitivität von Polynomialzeitreduktionen folgt dann, dass alle Probleme aus NP auch auf das betrachtete Problem reduzierbar sind. Die obige Definition erfordert streng genommen einen Existenzbeweis. Es ist nicht sofort ersichtlich, dass derartige Probleme überhaupt existieren. Es lässt sich aber leicht ein solches Problem konstruieren. Allerdings ist ein derart konstruiertes Problem kaum praxisrelevant. Cook konnte jedoch zeigen, dass das Erfüllbarkeitsproblem der Aussagenlogik NP-vollständig ist und hat damit für ein praxisrelevantes Problem den Nachweis geführt. Dieser Beweis konnte im Gegensatz zu anderen Problemen natürlich noch nicht wie oben dargestellt über die Transitivität von Polynomialzeitreduktionen geführt werden und musste direkt erfolgen.

Klassische Vertreter NP-vollständiger Probleme

- Erfüllbarkeitsproblem der Aussagenlogik (SAT)
- 3-SAT
- Max2SAT
- Knotenüberdeckungsproblem (Vertex Cover Problem)
- Cliquenproblem
- gerichtetes bzw. ungerichtetes Hamiltonkreisproblem
- Problem des Handlungsreisenden (Traveling Salesman Problem, kurz TSP)
- Behälterproblem (Bin Packing Problem, kurz BP)
- Rucksackproblem (Knap-Sack-Problem)
- PARTITION
- 3COLOR
- Exact Cover
- Subset Sum
- Bin Programming

NP-Äquivalenz

Der Begriff NP-Vollständigkeit ist nur für Entscheidungsprobleme definiert, also solche Probleme, die sich auf das Wortproblem einer formalen Sprache zurückführen lassen, für die als Antwort also nur entweder Ja oder Nein in Frage kommt. Für Optimierungsprobleme und Suchprobleme gibt es den Begriff der NP-Äquivalenz.

Approximation

Probleme die in NP liegen, lassen sich weiter in ihrer Komplexität unterteilen, je nach dem, wie gut sie sich approximativ lösen lassen. Das Graphen-Färbungsproblem lässt sich beispielsweise nur sehr schlecht approximativ lösen, während sich andere Probleme beliebig gut mittels so genannten Approximationsschemata approximieren lassen.

Starke und schwache NP-Vollständigkeit

Weiter kann man die NP-vollständigen Probleme noch einteilen in
- stark NP-vollständige und
- schwach NP-vollständige Probleme Ein NP-vollständiges Problem heißt stark NP-vollständig, falls es auch dann noch NP-vollständig ist, wenn die Eingabe nur aus Zahlen besteht, deren Größe polynomiell in der Eingabelänge beschränkt ist. Andernfalls heißt das Problem schwach NP-vollständig. Für stark NP-vollständige Probleme kann es - unter der Annahme NP ungleich P - noch nicht einmal so genannte pseudopolynomielle Algorithmen geben. Das sind Algorithmen, deren Laufzeit polynomiell ist, wenn die Größe aller in der Eingabe vorkommenden Zahlen polynomiell in der Eingabelänge beschränkt sind.

Literatur

- Michael R. Garey und David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1978. ISBN 0716710455
- Stephen A. Cook: The Complexity of Theorem Proving Procedures. In Annual ACM Symposium on Theory of Computing (STOC), pp 151--158, 1971.

Weblinks

-
- [http://www.nada.kth.se/~viggo/problemlist/compendium.html Compendium of NP-complete optimization problems] (englisch)

Siehe auch

- NP (Komplexitätsklasse)
- Komplexitätsklasse
- P/NP-Problem Kategorie:Komplexitätstheorie ja:NP完全 ko:NP-완전

NP-Äquivalenz

NP-Äquivalenz ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik. Es liefert eine prinzipielle Aussage darüber, ob Suchprobleme mit wachsender Anzahl der zu durchsuchenden Pfade oder Objekte noch praktisch lösbar sind, oder ob der benötigte Zeit- oder Speicheraufwand rasch in astronomische Dimensionen wächst. Die formale Definition des Begriffs lautet: Ein Suchproblem heißt NP-äquivalent, wenn es NP-leicht und NP-schwer ist. Ein NP-äquivalentes Problem ist genau dann in polynomieller Zeit lösbar, wenn P=NP ist. Siehe auch: NP-Vollständigkeit Kategorie:Theoretische Informatik Kategorie:Komplexitätstheorie

3 Sat

3sat ist der Name eines werbefreien öffentlich-rechtlichen Fernsehsenders. Gegründet wurde 3sat als deutschsprachiges Satelliten-Kulturprogramm vom deutschen ZDF, dem österreichischen ORF und der Schweizer Rundfunkanstalt SRG (heute SRG SSR idée suisse) von denen 3sat auch heute noch betrieben wird. Sendebeginn war am 1. Dezember 1984. Im Jahr 1990 stieg auch der DFF mit ein, und es wurde über eine Umbenennung in 4sat nachgedacht. Diese Überlegung wurde jedoch wieder verworfen und es blieb bei 3sat. Die Mitgliedschaft des DFF erlosch mit der Auflösung der Sendeanstalt gemäß des Einigungsvertrags am 31. Dezember 1991. Nach Einstellung ihres Satellitenkanals Eins Plus zum 1. Dezember 1993 folgte als Partner die ARD. 3sat wurde nun zum Vollprogramm. Der Sender wird über den Satellit Astra in Europa ausgestrahlt und ist auch über das Kabelnetz und DVB-T empfangbar. Federführend ist das ZDF, Entscheidungen werden im Konsens der Partner getroffen.

Magazine

- 3sat börse, freitags 21:30 Uhr
- DENKmal, ein Wissenquiz mit jeweils sechs Rätseln aus bedeutende Biografien, einmal im Monat, samstags 19:20 Uhr
- Delta, Das Denkmagazin, 14-täglich, donnerstags 21:00 Uhr, Moderation: Gert Scobel
- FOYER, Theatermagazin, 14-täglich, samstags 19:20 Uhr
- hitec Dokumentationen/Reportagen aus Wissenschaft und Technik, sonntags 16 Uhr
- Kulturzeit, wochentags 19:20 Uhr
- nano - die welt von morgen, wochentags 18:30 Uhr
- neues Computainment Magazin, samstags 17:00 Uhr
- tips&trends, domizil, mobil, mode, sportiv, samstags 17:30 Uhr Siehe auch: Liste der Fernsehsender

Weblinks

- [http://www.3sat.de/ 3sat-Website]
- [http://www.3sat.de/specials/72190/index.html Die 3sat Chronik – 20 Jahre 3sat] Kategorie:Fernsehsender

Bipartiter Graph

Ein einfacher Graph

G=(V,E)

(V Menge der Knoten, E Menge der Kanten) heißt in der Graphentheorie bipartit (auch paar), falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, so dass zwischen den Knoten innerhalb beider Teilmengen keine Kanten verlaufen. Das heißt für eine Kante

\ \in E

gilt entweder

v \in A

und

w \in B

oder aber

w \in A

und

v \in B

. Die Menge bezeichnet man dann als Bipartition des Graphen G. Der Graph

G

heißt sogar vollständig bipartit, falls eine Bipartition

\

existiert, für die jedes Paar

(a,b)

mit

a \in A

und

b \in B

die Kante

\

E

gehört. Einen solchen Graphen bezeichnet man auch als

K_

, wobei

m

und

n

die Anzahl der Knoten von

A

bzw.

B

sind.

Folgerungen

Die Teilmengen A und B sind also schon nach Definition stabile Mengen und die Bipartition impliziert eine mögliche 2-Färbung des Graphen. Umgekehrt sind alle 2-färbbaren Graphen bipartit. Für bipartite Graphen lassen sich viele Grapheneigenschaften mit weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist. Mit einem einfachen Algorithmus, der auf Tiefensuche basiert, lässt sich in linearer Zeit bestimmen, ob ein Graph bipartit ist, und eine gültige Partition bzw. 2-Färbung ermitteln.

Eigenschaften

- Die Paarungszahl entspricht der Knotenüberdeckungszahl.
- Mit dem Algorithmus von Hopcroft und Karp lässt sich in O(√nm) eine größte Paarung finden und darüber auch die Stabilitätszahl bestimmen.
- Der chromatische Index entspricht seinem Maximalgrad. Eine gültige Kantenfärbung lässt sich in O(nm) bestimmen.
- Ein regulärer bipartiter Graph besitzt ein perfektes Matching.
- Ein Graph ist genau dann bipartit, wenn er keinen Kreis ungerader Länge enthält.

Siehe auch

k-partiter Graph Kategorie:Graphentheorie

Paarungszahl

Definitionen

Sei G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und M eine Teilmenge von E. Man bezeichnet M als Paarung oder Matching von G, wenn je zwei beliebige verschiedene Kanten e₁ und e₂ disjunkt sind, d.h. mit verschiedenen Knoten inzident sind. Ein Knoten von G heißt von einer Paarung M überdeckt, falls es eine Kante in M gibt, die ihn enthält, d.h. die mit ihm inzident ist. Eine Paarung M von G nennt man maximal, wenn man keine weitere Kante e aus E zu M hinzufügen kann, so dass M zusammen mit e eine Paarung ist. Gibt es in G keine Paarung, die mehr Elemente als M enthält, so nennt man M größte Paarung. Ist jeder Knoten von V Element einer Kante von M (also von M überdeckt), so nennt man M eine perfekte Paarung. Die Anzahl Elemente einer größten Paarung nennt man Paarungszahl bzw. Matchingzahl. Einen k-regulären Teilgraphen von G nennt man einen k-Faktor, wenn er alle Knoten von G enthält. Die Kantenmenge eines 1-Faktors ist also offensichtlich eine perfekte Paarung. In kantengewichteten Graphen definiert man die Größe einer Paarung über die Summe ihrer Kantengewichte. Als größte gewichtete Paarung eines Graphen G bezeichnet man dann eine Paarung, die diesen Wert maximiert. In gerichteten Graphen und solchen mit Mehrfachkanten werden Paarungen nicht betrachtet. Ersteres, weil es bei Paarungen nicht auf die Richtung der Kanten ankommt, letzteres, weil von den Mehrfachkanten nur eine für eine Paarung in Frage kommt. Es spielt also keine Rolle, ob man den Graphen betrachtet, der entsteht, wenn man die Vielfachheiten von Mehrfachkanten auf 1 reduziert oder ob man den Originalgraph mit Mehrfachkanten betrachtet. Die nachfolgenden Definitionen dienen dem Verständnis der unten gegebenen Aussagen und Sätze. Einen Pfad P=v₁,...,v_k in einem Graphen G, bezeichnet man als alternierend bezüglich einer Paarung M von G, wenn für jedes i aus die Kante genau dann zu M gehört, wenn die Kante nicht zu M gehört, d.h. der Pfad P führt abwechselnd über Kanten die zu M gehören und solchen, die nicht zu M gehören. Sind zusätzlich und keine Kanten der Paarung M, so nennt man den Pfad P augmentierend bzw. Verbesserungspfad. Bezeichnet q(G) die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen G=(V,E), so nennt man def(G):=q(G-S)-|S| für ein Teilmenge S von V Defekt von G, falls q(G-U)-|U|≥q(G-S)-|S| für jede andere Teilmenge U von V gilt. G-S bzw. G-U bezeichnet dabei den Graphen, der entsteht, wenn man die Knoten von S bzw. U und ihre inzidenten Kanten aus G löscht.

Beispiel

Zusammenhangskomponente Dem Arbeitsamt liegen vier Stellenangebote und ebenso viele Stellengesuche vor. Dabei haben einige Arbeitssuchende mehrere Berufe angegeben, für die sie qualifiziert sind. Zur Veranschaulichung der Ausgangssituation kann ein bipartiter Graph gezeichnet werden (Abb. 1): dabei steht jeder Knoten in der linken Teilmenge für einen Arbeitssuchenden und jeder in der rechten für eine offene Stelle. Ist ein Arbeitssuchender mit einem Stellenangebot mittels einer Kante verbunden, so bedeutet das, dass er für den entsprechenden Beruf qualifiziert ist. So ist z. B. Laura in der Lage, als Kellnerin oder Stewardess zu arbeiten; Eduard und Klaus sind beide gelernte Schlosser und konkurrieren um die offene Stelle. bipartiter Graph Die Vermittlung von möglichst vielen Jobs ist ein Paarungs-Problem. Erneut werden die Stellengesuche und -angebote als Knoten eines bipartiten Graphen aufgefasst, diesmal stehen die Kanten jedoch für zugewiesene Jobs. Es sollen nun möglichst viele Kanten aus Abb. 1 übernommen werden, dabei darf an jedem Knoten allerdings höchstens eine Kante anliegen, denn natürlich kann für jedes Stellenangebot nur ein Bewerber angenommen werden, und jeder kann nur einen Job ausführen. Kann der Mitarbeiter des Arbeitsamtes nicht alle Stellengesuche und -angebote bearbeiten, weil ihm nicht genug Zeit zur Verfügung steht, so vermittelt er unter Umständen weniger Jobs, als möglich wären. Im Beispiel (Abb. 2) wurden nur zwei Jobs vermittelt, und zwar soll Eduard Schlosser werden und Laura Stewardess. Man spricht dennoch von einer Paarung (Matching), denn niemandem wurden zwei Jobs vermittelt, und keine Arbeitsstelle wurde zwei Bewerbern zugewiesen.
bipartiter Graph Doch auch wenn das Arbeitsamt alle Möglichkeiten berücksichtigt, ist es in diesem Fall nicht möglich, allen Arbeitssuchenden einen Job zu vermitteln. Die größte Paarung ist also in diesem Fall keine perfekte Paarung. Die Gründe dafür sind, dass die beiden gelernten Schlosser um eine einzige Stelle konkurrieren, während Maria entweder Taxifahrerin oder Kellnerin wird und somit eine Stelle offen bleibt. Dass eine perfekte Paarung nicht möglich ist, lässt sich mit dem Heiratssatz von Hall (siehe unten) beweisen. Das Arbeitsamt kann sich nun etwa entscheiden, Eduard die Stelle als Schlosser und Maria die als Taxifahrerin zu vermitteln (Abb. 3). Hier sieht man, dass es in einem Graphen mehr als eine größte Paarung geben kann: eine andere größte Paarung würde z. B. so aussehen, dass Klaus den Schlosserjob bekommt. bipartiter Graph Nun kontaktiert das Arbeitsamt Klaus und berichtet ihm von dem Problem. Um nicht arbeitslos zu werden, erklärt dieser sich bereit, statt als Schlosser als Taxifahrer zu arbeiten. Dadurch ist es möglich, jedem Arbeitssuchenden eine Stelle zu vermitteln (Abb. 4). Graphentheoretisch betrachtet, inzidiert also jeder Knoten mit genau einer Kante. Man spricht von einer perfekten Paarung. Eine perfekte Paarung ist nur dann möglich, wenn genauso viele Stellengesuche wie -angebote vorliegen, und, wie wir gesehen haben, selbst dann nicht immer.

Wichtige Aussagen und Sätze

Es lässt sich leicht zeigen, dass eine maximale Paarung eines Graphen G höchstens so viele Kanten wie eine größte Paarung in G enthält (jede größte Paarung ist auch eine maximale Paarung). Andererseits enthält eine größte Paarung in G höchstens doppelt so viele Kanten, wie eine maximale Paarung. Von Berge (1957) stammt ein leicht beweisbarer Satz, der besagt, dass eine Paarung M von einem Graphen G genau dann eine größte Paarung von G ist, wenn es keinen augmentierenden Pfad zu M gibt. Mit Hilfe dieses Satzes lässt sich leicht ein polynomieller Algorithmus entwerfen, der zu einem gegebenen Graphen ein größtes Matching findet, indem man nach augmentierenden Pfaden in einem Graphen sucht. In bipartiten Graphen lässt sich mit dem Algorithmus von Hopcroft und Karp in O(√nm) eine größte Paarung finden. Der Algorithmus basiert auf der Idee simultan mehrere Verbesserungspfade zu finden. Man zeigt leicht, dass die Knotenüberdeckungszahl eines Graphen mindestens so groß ist, wie seine Paarungszahl, aber höchstens so groß wie das 2-fache seiner Paarungszahl. Für bipartite Graphen konnte König (1931) zeigen, dass die Paarungszahl genau der Knotenüberdeckungszahl entspricht. Dies impliziert insbesondere polynomielle Algorithmen zur Bestimmung der Knotenüberdeckungszahl und in Folge auch der Stabilitätszahl eines bipartiten Graphen. Im allgemeinen sind diese Probleme NP-schwer. Der so genannte Heiratssatz von Hall (1935) besagt, dass in bipartiten Graphen G mit Bipartition genau dann eine Paarung M existiert, die jeden Knoten aus A überdeckt, falls für jede Teilmenge S von A gilt, dass ihre Nachbarschaft mindestens so groß ist wie S selbst. Der Name Heiratssatz rührt daher, dass es nach diesem Satz möglich ist, jede Frau zu verheiraten, falls es für jede Gruppe von Frauen mehr Männer gibt, die sich für wenigstens eine der Frauen in der Gruppe interessieren. Der Satz von Hall hat einige leicht ableitbare Konsequenzen. Gilt zum Beispiel zusätzlich, dass |A|=|B|, so besitzt G eine perfekte Paarung. In regulären Graphen ist diese Bedingung immer erfüllt. Ferner zeigt man leicht, dass auch die Heiratsbedingung |N(S)|≥|S| immer erfüllt ist, so dass jeder bipartite reguläre Graph eine perfekte Paarung besitzt. Diesen Satz konnte König schon 1916 beweisen (damals natürlich unabhängig vom Heiratssatz). Mit Induktion über k folgt dann auch leicht, dass ein k-regulärer Graph k disjunkte Paarungen besitzt, die zusammengenommen seine Kantenmenge ergeben. Hier wird der Sinn der Definition eines k-Faktors deutlich. In Graphen mit ungerader Knotenzahl gibt es offensichtlich keine perfekten Paarungen, da jede Paarung eine gerade Anzahl Knoten überdeckt. Die Defektformel von Berge (1958 ???) besagt jedoch, dass das 2-fache der Paarungszahl eines Graphen G der Anzahl Knoten von G abzüglich seines Defektes entspricht. Daraus leitet sich leicht ein Satz von Tutte (1947) ab, der besagt, dass ein Graph G=(V,E) genau dann eine perfekte Paarung besitzt, wenn für jede Teilmenge S von V gilt: q(G-S)≤|S|. Ebenfalls leicht folgt der schon 1891 von Petersen damals sehr aufwändig bewiesene Satz, dass ein kubischer Graph mit höchstens zwei trennenden Kanten ein perfektes Matching besitzt. In Graphen mit sehr vielen Kanten (sog. dichte Graphen) gibt es meistens auch eine (fast) perfekte Paarung. Algorithmisch interessant ist der Spezialfall, dass der Graph viele (fast) perfekte Paarungen besitzt und das Rechenverfahren die Aufgabe hat, eine solche Paarung zu finden. Kategorie:Graphentheorie Kategorie:Übersichtsartikel zur Graphentheorie

Polynomieller Algorithmus

In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn die Rechenzeit m mit der Problemgröße n nicht stärker als mit einer Polynomfunktion wächst. Die besondere Bedeutung der Polynomialzeit besteht darin, dass man sie als eine Grenze zwischen praktisch lösbaren und praktisch nicht lösbaren Problemen betrachtet. Der Aufwand für Probleme, die nicht in Polynomialzeit lösbar sind, explodiert derart schnell, dass sie schon für geringe Problemgrößen praktisch als unlösbar gelten müssen. Ob ein gegebenes Problem in Polynomialzeit lösbar ist, ist nicht von vornherein klar. So wurde erst 2002 von Agrawal, Kayal und Saxena ein Algorithmus (AKS-Primzahltest) angegeben, der in polynomialer Zeit entscheidet, ob eine vorgegebene natürliche Zahl ein Primzahl ist oder nicht. Das natürliche Verfahren, einfach alle möglichen Teiler durchzuprobieren, ist nicht polynomial.

Formale Definition

In mathematischer Schreibweise gemäß der Landau-Notation: m(n) = O(n^k), wobei k eine Konstante ist.

Polynomieller Algorithmus - ein Beispiel

Ein polynomieller Algorithmus ist ein Algorithmus, für den die Rechenzeit für die Lösung eines gegebenen Problems maximal polynomiell von der Problemgröße abhängt. Die Problemgröße bezieht sich dabei in der Regel auf die Eingabelänge. Beispiel: Ein Sortieralgorithmus, der für ein doppelt so großes Array konsistent etwa viermal so lange benötigt (allgemeiner: der für ein n-mal so großes Array n²-mal so lange braucht), ist ein quadratischer und somit - weil n² ein Polynom ist - ein polynomieller Algorithmus. Ein Algorithmus, der für eine Aufgabe beispielsweise 2ⁿ-mal so lange benötigt, wächst nicht polynomiell, sondern exponentiell (siehe exponentieller Algorithmus). Dies möchte man in der Regel vermeiden.

Superpolynomialzeit

Probleme, deren Berechnungszeit mit der Problemgröße stärker als mit einer Polynomfunktion wächst, heißen in Superpolynomialzeit lösbar, ein Beispiel dafür ist exponentielle Zeit (

m(n) = \Omega(c^n)

, c konstant).

Bezug zu den Komplexitätsklassen

Die Klasse aller Probleme, die sich auf einer deterministischen sequentiellen Maschine in Polynomialzeit lösen lassen, wird als P (von polynomial) bezeichnet. Die Klasse aller Probleme, die sich von einer (hypothetischen) nichtdeterministischen Maschine lösen lassen, wird als NP (von nondetermistic-polynomial time) bezeichnet. Es ist klar, dass

P \subseteq NP

, also P eine Teilmenge von NP ist. Eine bis heute unbewiesene Vermutung ist, dass wirklich beide Klassen verschieden sind, also

P \neq NP

. Diese Frage wird P/NP-Problem genannt und gilt als wichtigstes offenes Problem der Theoretischen Informatik.

Kritik

Die Polynomialzeit wurde bereits in den 1970er Jahren als Grenze zwischen den praktisch lösbaren und den praktisch unlösbaren Problemen angesehen. Es stellt sich die Frage, ob diese Sichtweise aufgrund der drastischen Verschnellerung moderner Computerhardware angepasst werden muss. Umgekehrt kann die Frage gestellt werden, ob nicht auch Polynome hohen Grades eine Aufwandsexplosion zur Folge haben, die praktisch nicht mehr zu handhaben ist. Die Polynomialzeit erscheint somit als recht willkürliche Grenze der Machbarkeit. Es lassen sich jedoch eine Reihe von Gründen für die Beibehaltung dieser Sichtweise anführen. Insbesondere hat sich herausgestellt, dass Probleme, die zunächst nur mit schlechtem polynomiellen Aufwand lösbar waren, jeweils recht bald auch mit niedrigem polynomiellem Aufwand (etwa vom Grad 2 oder 3) gelöst werden konnten. Offensichtlich bilden Polynomfunktionen eine so zusammenhängende Struktur, dass der algorithmische Aufwand meist auf Polynome niedrigen Grades zurückgeführt werden kann. Andererseits würde eine Beschränkung der praktisch machbaren Probleme etwa auf die in Linearzeit lösbaren Probleme eine derart große Gruppe bedeutsamer Algorithmen ausschließen, dass dies zumindest aus der Sicht der theoretischen Informatik kaum als gerechtfertigt erscheint. Dies bedeutet jedoch nicht, dass auch eine Polynomialzeit niedrigen Grades in der Praxis bereits als inakzeptabel gelten kann. Kategorie:Komplexitätstheorie ja:多項式時間

Reduktion (Theoretische Informatik)

Die Reduktion ist eine Methode der Theoretischen Informatik, mit der die Berechenbarkeit von Problemen oder die Entscheidbarkeit von Sprachen durch Umformung eines Problems in ein anderes verglichen werden kann. Am meisten wird die many-one-Reduktion verwendet. Weiterhin gibt es die one-one-Reduktion und die Orakel-Reduktion. = Definitionen = Eine Sprache

L'

ist auf eine Sprache

L

many-one reduzierbar, wenn eine totale, berechenbare Funktion

f: \Sigma^ -  \longrightarrow \Sigma^ -

existiert, mit

w \in L'

genau dann wenn

f(w) \in L

. Die Funktion

f

heißt dann die Reduktionsfunktion. Formal wird hierfür

L' \le_m L

geschrieben. Wenn

L' \le_m L

gilt und es eine injektive Reduktionsfunktion gibt, dann heißt

L'

auf die Sprache

L

one-one reduzierbar. = Beispiele =

1. Ein positives Beispiel:

:So lässt sich beispielsweise die Sprache aller Quadratzahlen ::

L_Q := \left\

:auf die Sprache aller Multiplikationen mit 2 Faktoren ::

L_M := \left\

:reduzieren, da über die Abbildung

f\colon \Z^2 \to \Z^3, \, (a,b) \mapsto (a,a,b)

jedes Wort aus

L_Q

in ein Wort aus

L_M

abgebildet werden kann und jedes Bild dieser Funktion

f\;

wiederum ein Urbild in

L_Q

besitzt. :Mit dieser Reduktion ist gezeigt, dass ein Algorithmus, welcher zwei natürliche Zahlen miteinander multipliziert, auch eine natürliche Zahl quadrieren kann, das Quadrieren kann also auf das Multiplizieren reduziert werden.

2. Ein negatives Beispiel:

Das Halteproblem ist nicht auf sein Komplement reduzierbar. Denn wäre das so, wäre es rekursiv entscheidbar. Es ist bekannt, dass das Halteproblem nur rekursiv aufzählbar ist und nicht rekursiv entscheidbar. = Reduktionen in der Komplexitätstheorie = Man möchte nicht nur qualitativ wissen, ob eine Reduktion existiert, sondern auch quantitativ den Aufwand zueinander in Bezug setzen. So will man ausdrücken: eine Sprache ist auf eine andere komplexitätsttheoretisch reduzierbar genau dann, wenn die eine nicht schwerer ist als die andere. Dafür werden an die Reduktionsfunktion f in der Hauptsache folgende Anforderungen gestellt:
- f ist in polynomieller Zeit berechenbar, so ist f eine Polynomialzeit-Reduktion.
- f ist auf logarithmischem Platz berechenbar, so ist f eine logarithmisch platzbeschränkte Reduktion. = Reduktionen in der Komplexitätstheorie =
- Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967
- Ein Nachdruck erschien bei MIT-Press Cambridge (Massachusetts), London (England), 1987. Kategorie:Theoretische Informatik Kategorie:Rekursionstheorie Kategorie:Komplexitätstheorie

Farbzahl

Glossar Graphentheorie#Chromatische Zahl

Kategorie:Graphentheorie

Diese Kategorie entspricht der :Kategorie:Mathematical Subject Classification 05Cxx, die allerdings genauer nach der Mathematical Subject Classification unterteilt ist. Siehe auch das Portal:Graphentheorie und das Wikipedia:WikiProjekt Graphentheorie Hauptartikel: Graphentheorie Kategorie:Diskrete Mathematik Kategorie:Logistik Kategorie:Theoretische Informatik ja:Category:グラフ理論 ko:분류:그래프 이론 th:Category:ทฤษฎีกราฟ

Kategorie:Komplexitätstheorie

Artikel über Komplexitätstheorie Kategorie:Theoretische Informatik

Sud-Ouest (Wein)

Als Weinbauregion steht Südwestfrankreich im Schatten von Bordeaux, obwohl es dort einige interessante Entdeckungen zu machen gibt. Der hier beschriebene Bereich umfasst die Regionen unterhalb von Bordeaux bis zu den Pyrenäen und in seitlicher Ausbreitung bis zur Stadt Toulouse.

Weinbaugebiete

Bergerac

Die Weinberge des Bergerac liegen im Périgord und grenzen an die von Bordeaux. Die allgemeine Appellation Bergerac umfasst das ganze Gebiet von ca. 90 Gemeinden auf denen auf 6876 ha Rotwein und Roséwein sowie auf 2960 ha Weißwein hergestellt wird. Wenn der Grundwein vom Zuckergehalt einen Alkoholgehalt von 11° garantiert, darf sich der Wein auch Côte de Bergerac nennen. Neben den allgemeinen Appelationen gibt es noch die folgenden AOC, die im gleichen Gebiet zugelassen sind:
- Pécharmant, bedeutet im Lokaldialekt bezaubernder Berg. Auf 409 ha werden ausschließlich Rotweine aus Malbec, Cabernet Sauvignon und Merlot angebaut. Dank verbesserter Kellertechniken werden hier ausgezeichnete Rotweine mit gutem Potential zur Lagerung hergestellt.
- Montravel, bekannt als Weißweingebiet darf es seit 2001 auch seine Rotweine als AOC verkaufen. 378 ha bestockte Fläche
- Rosette, hier entstehen gerade einmal 80000 Flaschen Wein und ist somit sehr selten anzutreffen.
- Saussignac, auf 98 ha entstehen feine Süßweine, moelleux genannt
- Monbazillac, hier werden große Süßweine im Stile eines Sauternes hergestellt. Die Qualität hängt von der Entwicklung der Edelfäule (Botrytis cinerea) ab. 2500 ha Rebland stehen zur Verfügung.

Madiran bzw. Pacherenc du Vic-Bilh

In Madiran dominiert die Tannat-Rebe, die mächtige, tanninstarke Rotweine mit langer Lagerungsfähigkeit hervorbringt. Im Jahr 2002 waren 1410 ha mit den roten Rebsorten bestockt. Der Tannat wird häufig mit Cabernet Sauvignon oder Cabernet Franc verschnitten. Die Weißweine des gleichen Gebiets heissen Pacherenc du Vic-Bilh und werden aus den Rebsorten Arrufiac, Manseng, Courbu, Sauvignon Blanc und Sémillon gekeltert. Die Weine sind sehr reich an verschiedenen Aromen wie Mandel, Haselnuss und tropischen Früchten und werden gerne in der trockenen Form als Apéritifwein gereicht. Daneben werden auch süße Weine angebaut.

Cahors

In Cahors wird als Leitrebe die Malbec neben dem Merlot und der Tannat Rebe verwendet. Im 19. Jahrhundert galt dieser Wein als die größte Konkurrenz des Bordeaux, und mittlerweile versuchen einige Betriebe mit Erfolg, an diese Tradition anzuschließen. Cahors hat seit 1971 den Status einer AOC. Wein wird jedoch schon seit der Besetzung durch die Römer um ca. 50 v.Chr. angebaut. Papst Johannes der XXII liess in der Nähe seines Amtssitzes von Avignon die Lagen des Châteauneuf-du-Pape durch Winzer des Cahors bewirtschaften. In der Blütezeit waren ca. 20.000 ha mit Reben bepflanzt. Der Befall der Reblaus sowie schwere Fröste im Jahr 1956 sorgten fast für das Aus des Weinbaus. Seither wurden die bestände wieder vorsichtig erweitert und vorrangig in den Mäandern des Flusses Lot angepflanzt. Heute (im Jahr 2002) stehen wieder 4450 ha Rebland zur Verfügung.

Gaillac

Südlich von Cahors schliesst sich das Gebiet des Gaillac an. Ähnlich wie Cahors ist dieses Gebiet gleich weit von Mittelmeer und Atlantik sowie nahe bei Toulouse gelegen. Seit 1938 gibt es eine AOC für Weißwein, seit 1970 wurden auch Rotwein und Rosé mit aufgenommen. Insgesamt 3730 ha Rebland sind in dieser Appellation bestockt, 73 Gemeinden teilen sich diesen Bestand.

Fronton

Marcillac

Tursan

Im Bereich Tursan( 27 Dörfer, 280 ha Rebfläche) werden süffige Rotweine hergestellt, die eine gute Qualität bei gutem Preis-Leistungsverhältnis aufweisen. Spezialität von Tursan ist jedoch ein Weißwein aus der lokalen Rebsorte Baroque. Tursan hat den Status einer VDQS.

Jurançon

Der Jurançon ist ein rassiger, langlebiger Weißwein, der trocken oder süß ausgebaut werden kann.

Côtes-de-Duras, Côtes du Marmandais, Buzet

Die Côtes-de-Duras sind die natürliche Verlängerung der Bordeauxregion Entre-Deux-Mers. Aufgrund der Nähe zum Bordeaux findet man hier die gleichen Rebsorten. Auf 2009 ha werden seit der Anerkennung zur AOC im Jahr 1937 vorrangig mittlerweile gute trockene als auch süße Weißweine ausgebaut. Die Qualität der Rot- und Roséweine hat auch schon sehr gutes Niveau erreicht. In der AOC (seit 1973) Buzet wird auf 1996 ha fast auschließlich Rotwein hergestellt, obwohl auch Weißwein und Rosé zugelassen sind.

Irouléguy

Kategorie:Weinbaugebiet Kategorie:Geographie (Frankreich)

Nurkowanie gry sportowe hoteles en Praga Hotel in Sofia diety

:: RELATED NEWS ::

Ouro Preto
Ouro Preto er en by i delstaten Minas Gerais i den sørøstlige regionen av Brasil. Byen ble grunnlagt i 1711 under navnet Vila Rica do Ouro Preto (Byen som er rik på svart gull). Ouro Preto ligger i fjellene Serra do Espinhaço og fungerte som sentrum i jakten på gull i delstaten. Byen har bevart sitt koloniale preg og er med på UNESCO

Austro-Daimler
right Austro-Daimler var en bilmodell og senere et bilmerke produsert i Østerrike fra 1899 til 1934. Fabrikken lå i nærheten av Wiener-Neustadt og var opprinnelig en del av den tyske Daimler-fabrikken. Selskapet ble uavhengig i Minas Gerais i den sørøstlige regionen av Brasil. Byen ble grunnlagt i 1711 under navnet Vila Rica do Ouro Preto (Byen som er rik på svart gull). Ouro Preto ligger i fjellene Serra do Espinhaço og fungerte som sentrum i jakten på gull i delstaten. Byen har bevart sitt koloniale preg og er med på UNESCO

Skur
Et skur er en mindre bygning som i hovedsak brukes til å oppbevare ting i. Skur pleier å være mindre solide en vanlige hus og har lite eller ingen isolasjon, da de ikke er til for å oppholde seg i over lengre tid. Skur pleier vanligvis ikke å ha vinduer. Det er alt etter størrelsen på skuret. Hva oppbevarer man i skur? Skur kan hovedsakelig benyttes til å ha spader og annet verktøy som man bruker ute. Da slipper man å gå inn for å hente det(Nå har flesteparten en stor kjeller som dette oppbevares i). Man hadde gjerne ikke noe s�

Leah Isadora Behn
Leah Isadora Behn (født 8. april 2005) er datter av prinsesse Märtha Louise av Norge og Ari Behn. Hun ble født på parets landsted, Bloksberg på Hankø i