Archiv der Kategorie: Graphentheorie

Jeder liebt jeden: Prädikatenlogik – Wikipedia

https://de.m.wikipedia.org/wiki/Pr%C3%A4dikatenlogik

und vor allem sich selbst.
Interessante Basis für einen Chatbot.
Stichworte für meinen nächsten „Hirnsturm“:
Kurzzeitgedächtnis KG – Logs
Langzeitgedächtnis LG – DB, txt-files
Lernen durch NN, Lehrer, Vergleich, Objekt- (Fakt)-DB, i18, news, def. Wikipedia, Twitter.

(472)

Die aktuelle Emanzipation der Sprache, ein Spiegelbild des dekadenten Verfalles einer Kultur?

@Ich bin weder ein Sprachwissenschaftler noch ein Experte aus einem verwandten Bereich, aber ich habe eine eigene Meinung. Diese ist zwar vielleicht nicht nur eigen sondern auch eigen im Sinne von eigenartig, aber aus meiner Sicht so klar und deutlich, dass man sicher kein Experte irgend einer Art sein muss, um meine Logik zu verstehen.
Seit Jahrzehnten gefällt mir der Ausspruch von Eccles, der meint, dass im sprachlichen Ausdruck subjektive Denkprozesse immerhin einen gewissen objektiven Status bekämen. Daher finde ich es wichtig, wenn Politiker, Personen in der Öffentlichkeit, Vorgesetzte, Ausbildner, Lehrer, Eltern und andere mehr bedacht mit ihren Worten umgehen. Grundsätzlich sollte das natürlich jeder, aber Personen mit einer bestimmten Verantwortung sollten sich dessen besonders bewußt sein. Sprachliche Verrohung, verbale Aggression und Diskriminierung verabscheue und bekämpfe ich – am meisten bei mir selbst.
Wenn bestimmte Ausdrücke und Bezeichnungen neu definiert werden, finde ich das sehr gut und sinnvoll, eine Tabuisierung oder gar ein Verbot bestimmter Wörter, denke gerade an Neger, halte ich allerdings fürg- dummen und sinnlos, ausgenommen in der EDV, wo man leicht Wörter verbieten kann. Hier denke ich vor allem an Maßnahmen gegen Spam und Wörter wie Viagra, obwohl diese in Formen wie z.B. V-I-A-G-R-A manchmal gar nicht so leicht automatisch zu erkennen sind.
Viele lateinische Wörter sind heute mit einer nahezu gegenteiligen Bedeutung im Umlauf und wenn ich an naturwissenschaftliche Berufe denke, die zum Beispiel „Psych…“ enthalten, so sind diese zwar vielleicht historisch gewachsen, aber trotzdem eine Schande für die gesamte Gesellschaft, da wissenschaftliche Arbeit meines Erachtens Definitionen voraussetzt. Für Wörter wie Psychologe, Psychiater, Psychopath und so weiter, würde sich meiner Meinung nach eine Neudefinition, ein Tabu oder gar ein Verbot eventuell als sinnvoll erweisen, aber auch nur eventuell und wenn wir wirklich keine anderen Sorgen mehr haben.
Die Anpassung des grammatikalischen Geschlechts an dem natürlichen und die sprachverhunzende, halbherzige Feminisierung halte ich nicht eventuell für ein Zeichen des dekadenten Verfalls einer Sprache und Kultur, sondern ganz sicher. Dieser Schildbürgerstreich ist bei mir unbedingt in den Top Ten aller Schildbürgerstreiche. Wenn schon, dann müsste man konsequent und wissenschaftlich vorgehen und mit den Substantiven beginnen. Das Erde, das Mond und das Sonne wären richtig und das Kind ist eine Diskriminierung, welche sofort verboten gehörte. Es kann nur die Mädchen und der Bube geben, aber kein sächliches Kind. Was usere Experten dann bei Mücken, Fliegen und Schlangen machen weiß ich nicht, aber vielleicht darf man dann von Lebewesen einfach nicht mehr sprechen, wenn man ihr natürliches Geschlecht nicht erkennen kann.
Hoch leben alle GermanistInnen, SprachreformerInnen und PolitierInnen, die diesen Wahnsinn voran treiben, statt sich um eine Anpassung der Sprache an moderne Technologien, exakte Definitionen, weniger Redundanz usw. zu kümmern. Meiner Meinung nach haben sehr viele Probleme ihre Ursache in Missverständnissen, die durch die Unzulänglichkeit unserer Sprache zustande kommen. Dabei spielt Schönschrift, Schreibschrift, Schulschrift, Groß- und Kleinschreibung nur insofern eine Rolle, weil in der Zeit mit der man diesen dummen Spielereien nachgeht, in Druckschrift längst sinnvolle Lösungen erreicht hätten werden können.
Ja, vielleicht eine sehr eigene Meinung, aber eben meine eigene. Was ich von den Rechtschreibreformen und PISA-Studien halte, weiß mit Sicherheit schon jeder, der ab und zu hier vorbei kommt. Daher genügt es mir hier, die Schlagworte zu erwähnen.


Während ich den Artikel schrieb, diskutierte ich über dieses Thema und ich dachte noch einmal darüber nach. Nachdenken ist nämlich meine große Stärke. 😉
Als Ergebnis kann ich jetzt zugeben, dass ich mich, meine Kultur und Sprache in Gefahr sah, wegen kleinen Änderungen, die eigentlich nur eine Diskriminierung beheben.
Trotzdem erwarte ich von Germanisten und Sprachreformer eigentlich mehr, denn die Sprache ist meiner Meinung nach sehr unzulänglich und sollte verbessert werden, damit wenigstens auf Sachebene im Vier-Seiten-Modell sollten die Möglichkeiten für Missverständnisse verringert wird (klare neue Definitionen, logische Grammatik, Anpassung an neue technische Gegebenheiten …).
Erwähnenswert finde ich hier das Vier-Seiten-Modell (auch Nachrichtenquadrat, Kommunikationsquadrat oder Vier-Ohren-Modell) von Friedemann Schulz von Thun ist ein Modell der Kommunikationspsychologie, mit dem eine Nachricht unter vier Aspekten oder Ebenen beschrieben wird: Sachinhalt, Selbstoffenbarung, Beziehung und Appell.

(661)

Testbeispiele

zurück zu Allgemeines

Testbeispiele

1 a) Wie ist die Isomorphie zwischen zwei Graphen definiert?

A: Eine bijektive Abbildung von V1 auf V2 heißt Isomorphismus von X1 auf X2, wenn gilt:

[x,y] ⇔ [ρ(x), ρ(y)] ∈ E2

Untersuchen sie folgenden Graphen paarweise auf Isomorphie.

Existiert zwischen zwei Graphen ein Isomorphismus, so geben Sie diesen an, andernfalls formulieren Sie eine Begründung, warum kein Isomorph ismus existiert.

A: Der Knoten 3 weist Grad 5 auf, weshalb der 1. und der zweite bzw. der 1. und der 3. Graph nicht isomorph sind.

Der 3. und 4. Graph kann auch nicht isomorph sein da die Anzahl der Knoten gleichen Grades unterschiedlich ist.

2) Gegeben sind die beiden Graphen X und Y:

X: V(X) = {1,2,3,4,5,6,7,8}          E(X) = {[x,y]| y teilt x}

X: V(Y) = 1,3,4,5}                      E(Y) = {[x,y] y größer x}

a)     Zeichnen sie die beiden Graphen und bilden Sie deren Vereinigung und Durchschnitt.

b)     Das Komplement Zc eines Graphen ist wie folgt definiert:

V(Zc) = V(Z)

E(Zc) = {[x,y] | x ¹ y, [x,y] Î E(Z)}

Stelle das Komplement des Graphen X dar.

 

3) Bestimmen Sie (algorithmisch) alle Blöcke, Artikulationen und Brücken des Graphen X.

Bestimmen Sie den durchmesser der von K(4) aufgespannten Komponente von X und skizzieren Sie außerdem alle Teilgraphen von X – {5,6,7,8,9,10,11,12,13,14}.

nach oben

(429)

Graphentheoretische Algorithmen

zurück zu Allgemeines

1      Graphentheoretische Algorithmen

1.1  Algorithmus zur Konstruktion eines maximalen Matchings

Matching maximal Û es existiert kein erweiterter alternierender Weg.

Initialisierung:

Step1: Aufnahme von paarweise disjunkten Kanten in einer Menge M (soviele wie möglich).

i=0, Mo = M;

Iteration:

Step2: Gibt es einen erweiterten alternierenden Weg W des Matchings Mi, dan ist Mi+1 =

(Mi-W) È (W-Mi) (= Mi D  W).

goto Step 3

Gibt es keinen alternierenden Weg, so gogo Step 4.

Step3:  i=i+1, goto Step2

Abschluß:

Step4: Mi ist das maximale matching.

 

1.2  Algorithmus zur Untersuchung eines gerichteten Graphen auf Azyklizität

G azyklisch -> $ x mit d+(x) = 0

Algorithmus:

Step1: Wir markieren alle Punkte x mit d+(x) =0 mit der Marke +.

Step2: jeder Punkt mit der Eigenschaft, daß alle seine Nachfolger mit + markiert sind, wird auch mit + markiert. Step 2 wird so oft wiederholt, als neue Punkte markiert werden.

Step3. Tritt keine neue Marke auf:

Sind alle Punkte markiert, so ist der Graph G azyklisch.

Gibt es nicht markierte Punkte, so enthält der Graph G einen Zyklus.

Beispiel:

 

 

 

 

 

 

 

 

Azyklisch da alle Punkte markiert sind: 5+ 4+ 3+ 2+ 1+

 

 

 

 

 

 

 

 

 

nicht azyklixh, da nicht alle Punkte markiert sind: 4+

 

Weiterer Algorithmus für dieses Problem:

Streichen von Kanten, die in keinem Zyklus liegen. Kanten <x,y> mit d+(y) =0.

Step1: Kante <x,y> mit d+(y) = 0 wird gestrichen, solange noch Kanten gestrichen werden können.

Step 2: Es kann keine Kante mehr gestrichen werden:

a) keine Kante mehr vorhanden -> G ist azyklisch

b) es gibt noch Kanten -> G ist nicht azyklisch

 

Beispiel:

 

 

5

 

 

 

 

 

 

 

 

 

 

azyklisch, da alle Kanten gestrichen sind;

 

 

1.3   Algorithmus zur Bestimmung der Komponenten des starken Zusammenhangs

xo fest ausgewählt:

+ Markierung bekommen jene Knoten, die von x0 aus erreichbar sind

Markierung bekommen jene Knoten, von dennen x0 aus erreichbar ist

Step1: x0 beliebig auswählen (Komponente von x0 wird bestimmt)

x0 wird mit + und –  markiert

IND:= 0 (=Indikator, soll angeben, ob überhaupt in einem Durchlauf ein Knoten markiert worden ist)

Step2: Für alle x e V(X) wird untersucht, ob überhaupt ein Nachfolger – oder Vorgänger makiert worden ist.

Wir durchlaufen alle Kanten <x,y>:

a)     x wird + markiert. Ist y nicht mit + markiert, dann wird y mit + markiert, IND := 1.

b)     y wird mit – markeirt. Ist x nicht mit – markiert, dann wird x mit – markiert, IND:=1.

Step3:

Ist IND = 1, so IND:=0 and goto Step2.

Ist IND = 0, dann gehören zur Komponente von X genau jene Knoten, die mit + und mit – markiert sind.

Komponentennummer 1

Zur Bestimmung der übrigen Komponenten werden neue x0 –Algorithmen durchgeführt. Sind beim 1. Durchlauf alle Knoten mit + oder – markiert, dann ist der Graph G stark zusammenhängend.

 

1.4  Algorithmus zur Bestimmung des reduzierten Graphen

zunächst ein Algorithmus zur Bestimmung der Komponentennummer (KNR). KNR von x ist k(x).

V(GR) = {K1, ….Kr}

Bestimmung dr Knaten von GR.

Wir durchlaufen alle kanten <x,y> des Grqphen G.

Ist k(x) = k(y) -> nächste Kante untersuchen.

Ist k(x) ¹ k(y) -> <Kk(x), Kk(y)> e E(GR)

Netzwerke:

G = (V,E) gerichter, ungerichtete oder gemischte Graphen mit Kantenbewertungen.

b(<x,y>) = b(x,y)eR+

z.B. : Straßennetz : b(x,y) = Länge der Strecke <x,y>

oder Telefonnetz: b(x,y)= Kosten des Baus der „Strecke“  <x,y> (richtungsunabhängig)

typische Problemstellung zum Beispiel: kürzester Weg zwischen zwei Knoten a und b

 

1.5  Algorithmus zur Bestimmung des kürzesten Weges von einem Startknoten a zu allen übrigen Knoten x (MOORE)

G zusammenhängend, wenn mehrere kürzeste Wege zwischen a und b existieren, so wählen wir einen aus. Wenn eine Bahn existiert, so gibt es eine kürzeste. Der Algorithmus liefert eine kürzeste kantenfolge von a nach b.

Voraussetzung.

Es gibt keinen Zyklus mit negativer Bewertung (Bewertung eines Zyklus = S der Bewertung der Kanten) dies ist sicher erfüllt wenn b(x,y) eR+)

l(x) = die Länge des bisher gefundenen kürzesten Weges (am Ende: Länge des kürzesten Weges von a nach x)

V(x) = Vorgänger auf diesem Weg

s(x) =  Anzahl der Kanten in dem bisher kantenreichsten Weg

Step1: Anzs:= 0, l(a) := 0, V(a):=0, s(a):=0 für x ¹ a: l(x) := ¥, V(x) := ¥, s(x):= ¥

Step2: IND:= 0, Durchlaufen aller Punkte x des Graphen

2a) Ist s(x) = Anzs, so durchlaufen wir alle Kanten <x,y>.

2aa) Ist l(y) =< l(x) + b(x,y),

der bisher gefundene Weg ist nicht schlechter als der neue, goto Step2a

2ab) Ist l(x) > l(x) + b(x,y), dann wird

l(y):= l(x) + b(x,y),

V(y) := x

s(y) := Anzs +1

IND := 1, goto Step 2a

2b) Ist IND = 0, dann Ende erreicht.

l(b) = Abstand von a nach b = d(a,b).

Ist IND = 1, dann ist Anzs:= Anzs + 1, gogo Step 2

 

Typische Problemstellung zum 2. Beispiel . Legen von Leitungen mit minimalen Gesmtkosten. Jeder Knoten ist mit jedem verbunden. Vorraussetzung. G ist zusammenhängend, gesuchter Teilgraph = spanndender Baum mit minimaler Bewertung, B(T) =

 

 

1.6  Algorithmus zur bestimmung des minimalsten spannen den Baums (Algorithmus von Kruskal)

Step1: mark(x) = 0 für alle x e V(G), KNR:=0

Step2. kanten nach Bewertung aufsteigend sortieren

Step3: Durchlaufen der Kanten in dieser Reihenfolge <x,y>

Fall 1:) mark(x) = mark(y)

1a) mark(x) = 0, KNR:= KNR+1

     mark(x) := mark(y) := KNR, <x,y> e E(T)

1b) mark(x) ¹ 0 (Kante erzeugt Kreis) goto next Kante

Fall 2: mark(x) ¹ mark(y)

2a) mark(x) = 0, so <x,y > e E(T) und mark(x):= mark(y)

2b) mark(y) = 0, so <x,y > e E(T) und mark(y):= mark(x)

2a) mark(x) ¹ 0 und mark(y) ¹ 0, so wird <x,y > e E(T) bei allen z mit mark(z) = mark(y) wird mark(z):= mark(x)

Step 4: minimales Gerüst gefunden; ist G nicht zusammenhängend, so ist das minimale Gerüst ein Wald und die verschiedenen Komponenten sind durch verschiedene Werte von mark(x) gekennzeichnet.

 

Exzentrizität klären und bei Beispiel dazuschreiben

was ist d+ bei der def. des 2. Algorithmus bzw. der Azyklizität

(264)