www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Diskrete Mathematik" - stabile Menge & sein Polyeder
stabile Menge & sein Polyeder < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

stabile Menge & sein Polyeder: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 18:30 So 25.09.2011
Autor: student0815

Aufgabe
Sei [mm]P = \left \{ x \in \IR^n | x_i + x_j \leq 1, x_i \geq 0 , x_i \leq 1; \forall i=1,...,n \right \}[/mm] das zugehöriger Polyeder zum Problem der stabilen Menge. P' sei das zugehörige ganzzahlige Polyeder. ([mm]P' = conv (P \cap \IZ^n )[/mm] ).
Zeigen oder widerlegen Sie , ob die folgenden Ungleichungen für P oder P' gültig sind:
a.) [mm]x_i + x_j + x_k \leq 1[/mm]  
b.) [mm]x_i + x_j + x_k \geq 1[/mm]
c.) [mm]x_i + x_j - x_k \leq 1[/mm]


Hallo,
habe mir gerad mal Gedanken gemacht zum Thema Graphentheorie und ILP's und LP's.
Wenn man das Problem der stabilen Menge aus der Graphentheorie betrachtet, und in ein LP formuliert, sehe ich dass dann richtig, dass das POlyeder aussieht wie das des Standardsimplex???
aber nun zur wichtigeren Frage wegen den Ungelichungen a.) b.) und C.)
Meine Schätzung:
a.) Nein, die Ungleichung ist weder gültig für P, noch für P'.
b.) ja, die Ungleichung ist gültig für P und P'.
c.) Nein, für kein Polyeder gültig.

Sind die Aussagen so korrekt?
Wie kann man das beweisen, also bei Nein, klar durch gegenbeispiel aber b.) ??

Wäre dankbar für Hinweise.
Grüße
student



        
Bezug
stabile Menge & sein Polyeder: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:37 Mo 26.09.2011
Autor: Stoecki

also mir sind deine indices nicht klar. das polytop der stabilen mengen hängt auch von den kanten ab. ich würde da also sowas wie [mm] x_i [/mm] + [mm] x_j \le [/mm] 1 für i [mm] \in [/mm] N(j) schreiben (N(i):= Nachbarschaftsmenge von i. geht man davon aus, dass diese nachbarschaftsrelationen gefordert sind, bzw. die ungleichungen nur dafür definiert sind, dann dürfen zwei benachbarte knoten nicht in der menge sein. wie sieht das dann für andere soummen wie denen da unten aus? zulässigkeit zeigst du, indem du eine ungleichung dann einfach für einen allgemeinen graphen durchspielst (stichwort fallunterscheidung)

Bezug
        
Bezug
stabile Menge & sein Polyeder: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:44 Mo 26.09.2011
Autor: Stoecki

noch eine anmerkung. nein, das polyeder sieht nicht aus wie das standardsimplex. die leere menge ist eine stabile menge, aber der nullvektor ist kein element des polytops der stabilen mengen

Bezug
        
Bezug
stabile Menge & sein Polyeder: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:20 Do 29.09.2011
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]