Zeigen Sie, dass benachbart zu sein zwar symmetrisch ist, aber niemals reflexiv, wenn E ≠ ∅

Question

Aufgabe:

Es sei Γ = (E, K) ein Graph. Lesen Sie im Skript, 1.4.10 nach, was die Relationen benachbart und
verbindbar zu sein jeweils bedeuten.
Zeigen Sie, dass benachbart zu sein zwar symmetrisch ist, aber niemals reflexiv, wenn E ≠ ∅
und niemals transitiv, wenn K ≠ ∅

Es sei Γ = (E, K) ein Graph. Zwei Ecken x, y ∈ E heißen benachbart, wenn
{x, y} ein Kante ist. Benachbart zu sein ist eine Relation auf E.

Problem/Ansatz:

Ich weiß nicht wie ich das beweisen soll. Ich weiß dass E nicht die leere Menge enthalten soll, was wenn es drin wäre einfach ist zu beweisen da die leere Menge nicht auf sich selbst verweist. Im Grunde ist x,y∈E und xRx die Voraussetzung für Reflexivität und ich denke mal ich muss ein Gegenbeispiel finden. Also für die Reflexivität das nicht stimmt um die nicht Reflexivität zu beweisen, aber wie soll ich da anfangen?

Comments

Es sei Γ = (E, K) ein Graph.

Was ist E? Was ist K?

Ich weiß dass E nicht die leere Menge enthalten soll

Woher weißt du das?

---

Ich komme mit den Begriffen nicht klar. "benachbart" - vermute ich - heißen zwei Ecken, wenn sie eine Kante bilden. In einem einfachen Graphen - oder habt Ihr etwas anderes definiert? - gibt es keine Schleifen, also Kanten, die eine Ecke mit sich selbst verbinden?? So gesehen wäre die Aufgabe trivial.

Hat sich durch Oswalds Antwort erledigt

---

Weil das mit E in der Aufgabenstellung steht. E und K sind genau so gegeben und ja des mit der Kante stimmt. Ich glaube man muss zeigen, dass es keine Kanten gibt die auf sich selbst zeigen. Ich hab die Aufgabe so bekommen, alles was da steht ist was ich weiß und zur verfügung hab.

---

alles was da steht ist was ich weiß und zur verfügung hab.

Nee. Du kannst und sollst in Deinem Skript nachschauen, ob Ihr "Graph" so definiert habt, dass Oswalds Antwort zutriff.....

Answer 1

Wenn x = y ist, dann ist {x,y} eine einelementige Menge.

Ich vermute, die Kanten sind als zweielementige Teilmengen von E definiert worden.

Comments

E sind die Ecken und K die Kanten. Die Kanten bestehen aus zwei Ecken x,y∈E. Die Kante dazu wäre {x,y}∈K. Kann es sein: Wenn E nicht leer und der Graph symmetrisch dann kann der Graph nicht reflexiv sein da die Kante aus einer Menge besteht. Da müssen, nehm ich hoffentlich richtig an zwei Elemente drin sein, also kann es nicht nur ein Element enthalten weil {1,1}={1} ist und die Elemente damit unterschiedlich sein müssen.

Def.

Ein Kantenzug der Länge l ∈ N0 von x ∈ E nach y ∈ E ist eine Sequenz
von Ecken x₀, x₁, . . . , x_l−1, x_l, wobei x₀ = x und x_l = y, sodass für jedes i ∈
{0, . . . , l − 1} die Ecken xi und xi+1 benachbart sind

---

Die Kanten bestehen aus zwei Ecken

Damit ist wegen der "zwei" üblicherweise gemeint, dass die Ecken einer Kante verschieden voneinander sein müssen.

da die Kante aus einer Menge besteht

Aber {1,1} ist eine Menge. Entscheidend ist, dass eine Kante eine zweielmentigen Menge ist und {1,1} eine einelementige Menge ist.