Return-Path: X-OfflineIMAP-2089985718-466d4c6f63616c496d6170-494e424f582e756e69: 1206518429-0965584260071-v5.99.7 Received: from compute2.internal (compute2.internal [10.202.2.42]) by store16m.internal (Cyrus v2.3.11-fmsvn14336) with LMTPA; Wed, 26 Mar 2008 03:13:25 -0400 X-Sieve: CMU Sieve 2.3 X-Spam-score: 0.0 X-Spam-hits: BAYES_50 0.001, UNPARSEABLE_RELAY 0.001, BAYES_USED global X-Spam-source: IP='141.26.64.15', Host='deliver.uni-koblenz.de', Country='DE', FromHeader='de', MailFrom='de' X-Resolved-to: thorn+uni@fastmail.fm X-Delivered-to: thorn+uni@fastmail.fm X-Mail-from: obermaie@uni-koblenz.de Received: from mx2.messagingengine.com ([10.202.2.201]) by compute2.internal (LMTPProxy); Wed, 26 Mar 2008 03:13:25 -0400 Received: from deliver.uni-koblenz.de (deliver.uni-koblenz.de [141.26.64.15]) by mx2.messagingengine.com (Postfix) with ESMTP id B176C1EC8ED for ; Wed, 26 Mar 2008 03:13:23 -0400 (EDT) Received: from localhost (localhost [127.0.0.1]) by deliver.uni-koblenz.de (Postfix) with ESMTP id 2B5C478980B3 for ; Wed, 26 Mar 2008 08:13:22 +0100 (CET) Received: from deliver.uni-koblenz.de ([127.0.0.1]) by localhost (deliver.uni-koblenz.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 22572-06; Wed, 26 Mar 2008 08:13:22 +0100 (CET) Received: from mail.uni-koblenz.de (mail.uni-koblenz.de [141.26.64.7]) by deliver.uni-koblenz.de (Postfix) with ESMTP id 0D4C37894B6A for ; Wed, 26 Mar 2008 08:13:22 +0100 (CET) Received: by mail.uni-koblenz.de (Postfix, from userid 96) id 0B0A63803BCC; Wed, 26 Mar 2008 08:13:22 +0100 (CET) Received: from mail.uni-koblenz.de ([unix socket]) by mail (Cyrus v2.2.12) with LMTPA; Wed, 26 Mar 2008 08:13:22 +0100 X-Sieve: CMU Sieve 2.2 Received: from deliver.uni-koblenz.de (deliver.uni-koblenz.de [141.26.64.15]) by mail.uni-koblenz.de (Postfix) with ESMTP id EDA8E3801775 for ; Wed, 26 Mar 2008 08:13:21 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by deliver.uni-koblenz.de (Postfix) with ESMTP id DF40078980B3; Wed, 26 Mar 2008 08:13:21 +0100 (CET) Received: from deliver.uni-koblenz.de ([127.0.0.1]) by localhost (deliver.uni-koblenz.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 22759-04; Wed, 26 Mar 2008 08:13:21 +0100 (CET) Received: from yamato.uni-koblenz.de (yamato.uni-koblenz.de [141.26.69.154]) by deliver.uni-koblenz.de (Postfix) with ESMTP id 147A57894B6A for ; Wed, 26 Mar 2008 08:13:21 +0100 (CET) Received: from [127.0.0.1] (localhost [127.0.0.1]) by yamato.uni-koblenz.de (Postfix) with ESMTP id EFC6F263BC for ; Wed, 26 Mar 2008 08:13:20 +0100 (CET) Message-ID: <47E9F790.70705@uni-koblenz.de> Date: Wed, 26 Mar 2008 08:13:20 +0100 From: Claudia Obermaier User-Agent: Thunderbird 2.0.0.12 (X11/20080226) MIME-Version: 1.0 To: Tassilo Horn Subject: Re: Frage zur Dissolution References: <87prtic2yh.fsf@uni-koblenz.de> In-Reply-To: <87prtic2yh.fsf@uni-koblenz.de> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Virus-Scanned: amavisd-new at uni-koblenz.de X-Virus-Scanned: amavisd-new at uni-koblenz.de Hallo, ich bin auch etwas verwirrt von dem Beispiel. Irgendwas ist da faul. Der Subgraph relativ zu {C,~A} sollte eigentlich ~A C v & C sein. Aber auch wenn der Subgraph so aussieht und nicht wie in deiner Lösung, ist das ganz kein c-Block. Denn wie du richtig bemerkt hast, macht der c-Pfad {~A,D} Probleme. Der schneidet den Subgraphen zwar, aber ist kein Cpfad. Also ist der obige Subgraph noch nicht einmal ein C-Block. Ich vermute, dass sich hier ein kleiner Fehler eingeschlichen hat. Wenn man das rechte C durch ein anderes Literal ersetzen würde, dann klappt das Beispiel. Dann wäre C v ~A der Subgraph relativ zu {C,~A} und das wäre dann tatsächlich auch ein "strong c-block". Gruß Claudia Tassilo Horn schrieb: > Hi Claudia, > > ich hab mal eine Frage zum Dissolutions-Paper. Auf Seite 508 unten > geht's um "strong blocks". Demnach ist ein Subgraph ein c-block, wenn > alle c-paths, die mindestens einen Knoten von H beinhalten, "durch H > durchgehen" (pass through H). Das ist der Fall, wenn die Knoten des > c-path, welche in H liegen, wiederum einen c-path in H bilden. > > So weit, so gut. Jetzt soll ein starker c-Block ein solcher sein, durch > den alle c-paths des Graphen laufen. Als Beispiel wird der Subgraph > relativ zu {C, ~A} angegeben. > > Wenn ich alles korrekt verstanden habe, so ist dieser Graph folgender > (~ = nicht, & = and): > > ~A > & > C > > Wenn man jetzt aber den c-path {~A, D} betrachtet, so würde ich meinen, > dass das ein Gegenbeispiel ist. ~A ist in dem vermeintlichen Block > enthalten, ist aber nur ein partieller c-path darin, denn er ist im > c-path {~A, C} komplett enthalten. > > Wo liegt mein Denkfehler? > > Viele Grüße, > Tassilo >