TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/20. VO 24.11.2005

Begriffe: einfacher Graph = ungerichteter Graph (keien Mehrfach., keine Schlingen)

• transitive Hülle (= transitiver Abschluss)

Am gerichteten, schlichten Graphen $G=\langle V,E\rangle$

Transitive Hülle: $G^{T}=\langle V,E\rangle$

wobei gilt: $(u,v)\in E_{T}:\Leftrightarrow$

Es existiert ein gerader Weg von u nach v im ursprünglichen Graphen G

(Graph 1)

Transitive Reduktion: $G_{R}$ heißt eine transitive Reduktion von G, falls $(G_{R})^{T}=G^{T}$ und $E_{R}\subseteq E$ minimal.

Algebra

Algebraische Grundbegrife

Definition: EIne Abbildung $\circ :M\times M\rightarrow M$ heißt zweistellige Operation (= binäre Operation) in M

Menge M ist beliebig

d.h. jedem Paar $(a,b)\in M\times M$ wird genau ein Element $a\circ b$ aus M zugeordnet

Beispiele:

• a + b in $\mathbb {Q}$
• a - b in $\mathbb {Q}$
• a * b in $\mathbb {Q}$
• a^b in $\mathbb {R} ^{+}$

Seien

• f: $D\rightarrow \mathbb {R}$
• g: $D\rightarrow \mathbb {R}$ Abb.

Def.: auf der Menge aller Abb. von $D\rightarrow \mathbb {R}$ eine binäre Operation + durch

$(f+g)_{(x)}=f(x)+g(x)$

$(f,g)\rightarrow f+g$

Punktweise erkl. Addition von Fkt.

• M ${\mathfrak {P}}(M)$

Binäre Operationen $\cap ,\cup ,\bigtriangleup ,\backslash$ auf ${\mathfrak {P}}(M)$

$(A,B(\rightarrow A\bigtriangleup B,\qquad A,B\in {\mathfrak {P}}(M)$

$a\circ b:=a*b{\text{ mod 4 }}$

binäre Operation auf $\mathbb {Z} _{4}$

durch Operationstafel vollständig beantwortbar

  0 0 1 2 3
  0 0 0 0 0
  1 0 1 2 3
  2 0 2 0 2
  3 0 3 2 1

Eigenschaften von $\circ$ bin. Op. auf M

• Assoziativität

$(a\circ b)\circ c=a\circ (b\circ c)\qquad \forall a,b,c\in M$

$(a^{b})^{c}\neq (a^{(b^{c})}$ i.A.

z.B. (2^3)^2 nicht gleich 2^(3^2)

$a^{b}$ nicht assoziativ $(\mathbb {R} )$

+,* auf $\mathbb {Q} assoziativ$

• Kommutativität

$a\circ b=b\circ a,\qquad \forall a,b\in M$

+,* sind auf $\mathbb {Q} ,\mathbb {R}$ kommutativ

• Existenz eines neutralen Elementes e

$a\circ e=e\circ a=a\qquad \forall a\in M$

d.h. e ein neutrales Element von $\circ$

betrifft $M=\mathbb {Q}$

• 0 neutral bei +
• 1 neutral bei *

• Existenz eines inversen Elements

sei $a\in M$, ein Element $a'\in M$ mit $a\circ a'=a'\circ a=e$ (e ist neutrales Elem.)

dann heißt a' inverses Element von A

Beispiel: $M=\mathbb {Q}$, Op. +

Es gibt $\forall a\in \mathbb {Q}$ ein inverses Element $a'\in \mathbb {Q}$

nämlich $a'=-a$

inverses Element *

inverses Element $\bigtriangleup$

• Distributivität Operationen $\circ$,*

$a\circ (b*c)=(a\circ b)*(a\circ c)\qquad \forall a,b,c\in M$

dann heißt $\circ$ linksdistributiv bez. *

$(b*c)\circ a=(b\circ a)*(c\circ a)\qquad \forall a,b,c\in M$

dann heißt $\circ$ rechtsdistributiv bez. *

Distributivität bez. + in $\mathbb {R}$

Eine Menge zusammen mit Operationen in M (n-stellige Operationen) heißt Algebraische Struktur (Abkürzung: Algebra)

z.B.: $\langle \mathbb {R} ,+,*,-,0,1,\rangle$

• +,* binäre Operation
• - einstellige Operation
• 0,1 n-stellige Operation

n-stellige Oprationen:

$(M\times M\times ...\times M)\rightarrow M$

(n mal ausgeführt)

$\circ$ Abb. v. $M^{n}\rightarrow M$

Def.: Menge M, binäre Operation $\circ$ in M, $\langle M,\circ \rangle$, heißt Gruppoid (manchmal sagt man, $\circ$ ist abgeschlossen)

d.h. $\forall a,b\in M:\exists a\circ b\in M$

• wenn $\circ$ assoziativ, dann $\langle M,\circ \rangle$ heißt Halbgruppe

• wenn $\circ$ ein neutrales Element besitzt (also e), dann heißt $\langle M,\circ ,e\rangle$ ein Monoid

• wenn $\forall a\in M$ ein inverses Element a' existiert, dann heißt $\langle M,\circ ,e,'\rangle$ eine Gruppe

• wenn $\circ$ kommutatiov, dann kommutative Gruppe (Abelsche Gruppe)