minimal imperfekte Berge-Graphen!? |
| 13.02.2009, 09:59 | Auf diesen Beitrag antworten » |
| noob222 | minimal imperfekte Berge-Graphen!? Hallo, ich habe zwei Aussagen: 1) Es gibt keine minimal imperfekte Berge-Graphen 2) Für jeden minimal impefekten Berge-Graphen gilt, dass sowohl Cliquenzahl als auch die Stabilitätszahl (max. Independent-Set) >= 4 sind. Dazu die Definitionen: Berge-Graphen sind perfekt, solange sie keine ungeraden Kreise >= 5 als induzierte Subgraphen besitzen. Ein Graph G ist minimal imperfekt falls G nicht perfekt ist, aber alle seine induzierten Subgraphen. Ein Split-Graph ist ein perfekter Graph, dessen Knoten sich in eine Clique und Independent-Set partitionieren lassen. Welche Aussage stimmt nun oben? Da Berge-Graphen perfekt sind, können sie nicht minimal imperfekt sein. Denn minimal imperfekt bedeutet ja, dass G nicht perfekt sein kann, aber alle induzierten Subgraphen dafür perfekt sind. Aber G ist ja schon Berge-Graph und somit perfekt und ebenfalls auch alle Subgraphen. Also stimmt die erste Aussage. Aber ich komme mit der zweiten Aussage nicht zu recht. Es ist doch ein Widerspruch zu der 1. Aussage oder nicht? Zudemm sind ja alle Graphen, die eine maximale Clique und Independent-Set >=4 besitzen ebenfalls Perfekt. Denn das sind genau die Graphen, die einen Split-Graphen repräsentieren. Also sind auch diese Graphen perfekt, und somit auch Berge-Graph. Was stimmt an der 2. Aussage nicht? Quelle zu der 2. Aussage: http://www.informatik.uni-rostock.de/~le...rch/2-split.pdf 2. Seite, 2. Zeile von oben. Danke |
|
|
|
|
|
