aussagenlogik und graph < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:07 Mi 25.10.2006 | | Autor: | herates |
| Aufgabe | Jedem (ungerichteten) Graphen mit Knoten 1, . . . , n ordnen wir eine aussagenlogische Interpretation in folgender Weise zu:
Jedem Paar i < k von Knoten wird eine Variable [mm]X_i,k[/mm] zugeordnet,
die genau dann den Wert 1 erhält, wenn es eine Kante zwischen i und k gibt.
(a) Geben Sie für n = 5 eine Formel an, welche beschreibt, dass der Grad des Graphen mindestens drei ist, d. h. es gibt einen Knoten mit mindestens drei Nachbarn.
(b) Konstruieren Sie für beliebige n und k Formeln [mm]\mu_n,k[/mm], die ausdrücken, dass der Graph k regulär ist.
(c) Geben Sie für beliebige n eine Formel n an, die beschreibt, dass der Graph ein vollständiger bipartiter Graph ist. |
okay, hier steh ich total auf dem schlauch.
a) ist ja nur spezieller als b) also auf zu b)
hä?
iteriere ich jetzt so: [mm]\bigcup_{j=1}^{i} \bigcap_{j=1}^{k} \land X_i,k[/mm]??
wobei das natürlich nicht schnitt und vereinigung sondern und und oder sind.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:04 Mi 25.10.2006 | | Autor: | Frank05 |
> (a) Geben Sie für n = 5 eine Formel an, welche beschreibt,
> dass der Grad des Graphen mindestens drei ist, d. h. es
> gibt einen Knoten mit mindestens drei Nachbarn.
> (b) Konstruieren Sie für beliebige n und k Formeln
> [mm]\mu_n,k[/mm], die ausdrücken, dass der Graph k regulär ist.
> okay, hier steh ich total auf dem schlauch.
> a) ist ja nur spezieller als b) also auf zu b)
So kannst du das nicht sagen. a) ist nicht ein Spezialfall von b). Es gibt Graphen deren Grad drei ist, die aber nicht drei regulär sind (denn dafür müssen alle Knoten mind. Grad drei haben).
Fang also besser bei a) an, wo du eine Formel entwickelst, die für einen Knoten verlangt, dass er Grad drei oder mehr hat und für b) kannst du das dann mit Hilfe dieser Formel für alle Knoten verunden.
Für a) kannst du von einem Graphen mit 5 Knoten ausgehen. Für jeden Knoten kannst du nun eine Teilformel aufstellen für den Grad und diese Formeln werden mit oder verknüpft.
Du kannst das Ganze also jetzt vereinfachen auf einen bestimmten Knoten und musst für ihn eine Formel bestimmen, die wahr wird wenn der Grad drei oder mehr ist. (Ich nehme an Schleifen sind nicht erlaubt im Graphen) Dieser Knoten hat nun 4 Nachbarn und soll mit mindestens 3 verbunden sein. Dann gibt es also 4 Möglichkeiten, dass er genau mit 3 anderen verbunden ist und eine (in der Formel nicht mehr zu berücksichtigende) Möglichkeit, dass er mit allen 4 Nachbarn verbunden ist. Diese Fälle kannst du nun ganz konkret durchspielen und wieder verodern:
[mm](x_{1,2} \wedge x_{1,3} \wedge x_{1,4}) \vee (x_{1,2} \wedge x_{1,3}, \wedge x_{1,5}) \vee \dots[/mm]
Mit diesen Ideen im Hinterkopf kannst du nun Schritt für Schritt die gesuchte Formel zusammenbauen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:39 Mi 25.10.2006 | | Autor: | herates |
Das habe ich mir auch überlegt, doch dann habe ich ja wirklich zu 5 knoten 4 Möglichkeiten das er den Grad 3 hat. macht also 20 oder vekrnüpfungen mit jeweils 4 und verknüpfungen. zeimlicher overhead finde ich
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:15 Mi 25.10.2006 | | Autor: | Frank05 |
> zeimlicher overhead finde ich
Gewöhn dich am besten daran. Es kommt sehr häufig in der Informatik vor, dass man nur daran interessiert ist, ob etwas geht und es nicht wichtig ist, ob man nun einiges an overhead dafür aufwenden muss oder nicht. Insbesondere in der Aussagenlogik ist das immer wieder der Fall bei Aufgaben vom Typ 'geben Sie eine Formel an'.
Also erstmal die Aufgabe bearbeiten und dann kannst du in manchen Fällen immer noch zusätzlichen Gehirnschmalz reinstecken, um eine elegantere Lösung zu finden. Das ist aber meistens nicht gefragt.
|
|
|
|
