Минимальные сепараторы в структурах зависимостей. Свойства и идентификация
В настоящей работе рассматриваются вероятностные модели зависимостей, структурированные ациклическими орграфами (АОГ-модели). Различают три основные разновидности АОГ-моделей: байесовские сети, гауссовы сети и гибридные сети. В байесовских сетях переменные — номинальные (дискретные), в гауссовых — д...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/44271 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Минимальные сепараторы в структурах зависимостей. Свойства и идентификация / А.С. Балабанов // Кибернетика и системный анализ. — 2008. — № 6. — С. 17-32. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-44271 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-442712013-05-28T03:11:32Z Минимальные сепараторы в структурах зависимостей. Свойства и идентификация Балабанов, А.С. Кибернетика В настоящей работе рассматриваются вероятностные модели зависимостей, структурированные ациклическими орграфами (АОГ-модели). Различают три основные разновидности АОГ-моделей: байесовские сети, гауссовы сети и гибридные сети. В байесовских сетях переменные — номинальные (дискретные), в гауссовых — действительные (зависимости — линейные). В гибридных сетях используются оба типа переменных. Результаты статьи охватывают все разновидности АОГ-моделей, так как базируются только на общих свойствах этих моделей — ацикличности орграфа и критерии d-сепарации. 2008 Article Минимальные сепараторы в структурах зависимостей. Свойства и идентификация / А.С. Балабанов // Кибернетика и системный анализ. — 2008. — № 6. — С. 17-32. — Бібліогр.: 15 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/44271 007:681.3.00 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Балабанов, А.С. Минимальные сепараторы в структурах зависимостей. Свойства и идентификация Кибернетика и системный анализ |
| description |
В настоящей работе рассматриваются вероятностные модели зависимостей, структурированные ациклическими орграфами (АОГ-модели). Различают три основные разновидности АОГ-моделей: байесовские сети, гауссовы сети и гибридные сети. В байесовских сетях переменные — номинальные (дискретные), в гауссовых — действительные (зависимости — линейные). В гибридных сетях используются оба типа переменных. Результаты статьи охватывают все разновидности АОГ-моделей, так как базируются только на общих свойствах этих моделей — ацикличности орграфа и критерии d-сепарации. |
| format |
Article |
| author |
Балабанов, А.С. |
| author_facet |
Балабанов, А.С. |
| author_sort |
Балабанов, А.С. |
| title |
Минимальные сепараторы в структурах зависимостей. Свойства и идентификация |
| title_short |
Минимальные сепараторы в структурах зависимостей. Свойства и идентификация |
| title_full |
Минимальные сепараторы в структурах зависимостей. Свойства и идентификация |
| title_fullStr |
Минимальные сепараторы в структурах зависимостей. Свойства и идентификация |
| title_full_unstemmed |
Минимальные сепараторы в структурах зависимостей. Свойства и идентификация |
| title_sort |
минимальные сепараторы в структурах зависимостей. свойства и идентификация |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2008 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/44271 |
| citation_txt |
Минимальные сепараторы в структурах зависимостей. Свойства и идентификация / А.С. Балабанов // Кибернетика и системный анализ. — 2008. — № 6. — С. 17-32. — Бібліогр.: 15 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT balabanovas minimalʹnyeseparatoryvstrukturahzavisimostejsvojstvaiidentifikaciâ |
| first_indexed |
2025-07-04T02:43:03Z |
| last_indexed |
2025-07-04T02:43:03Z |
| _version_ |
1836682559578177536 |
| fulltext |
ÓÄÊ 007:681.3.00
À.Ñ. ÁÀËÀÁÀÍÎÂ
ÌÈÍÈÌÀËÜÍÛÅ ÑÅÏÀÐÀÒÎÐÛ Â ÑÒÐÓÊÒÓÐÀÕ ÇÀÂÈÑÈÌÎÑÒÅÉ.
ÑÂÎÉÑÒÂÀ È ÈÄÅÍÒÈÔÈÊÀÖÈß
Êëþ÷åâûå ñëîâà: àöèêëè÷åñêèå îðãðàôû, ÀÎÃ-ìîäåëü âåðîÿòíîñòíûõ çàâèñè-
ìîñòåé, óñëîâíàÿ íåçàâèñèìîñòü, áàéåñîâñêèå ñåòè, êðèòåðèé d-ñåïàðàöèè,
êîëëàéäåð, öåïü, ëîêàëüíî-ìèíèìàëüíûå ñåïàðàòîðû, èäåíòèôèêàöèÿ ðåáåð,
ïîäáîð ñåïàðàòîðîâ, íåîáõîäèìûå òðåáîâàíèÿ ê ÷ëåíàì ëîêàëüíî-ìèíèìàëü-
íûõ ñåïàðàòîðîâ.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåé ðàáîòå ðàññìàòðèâàþòñÿ âåðîÿòíîñòíûå ìîäåëè çàâèñèìîñòåé,
ñòðóêòóðèðîâàííûå àöèêëè÷åñêèìè îðãðàôàìè (ÀÎÃ-ìîäåëè). Ðàçëè÷àþò òðè
îñíîâíûå ðàçíîâèäíîñòè ÀÎÃ-ìîäåëåé: áàéåñîâñêèå ñåòè, ãàóññîâû ñåòè è ãèá-
ðèäíûå ñåòè. Â áàéåñîâñêèõ ñåòÿõ ïåðåìåííûå — íîìèíàëüíûå (äèñêðåòíûå), â
ãàóññîâûõ — äåéñòâèòåëüíûå (çàâèñèìîñòè — ëèíåéíûå). Â ãèáðèäíûõ ñåòÿõ èñ-
ïîëüçóþòñÿ îáà òèïà ïåðåìåííûõ. Ðåçóëüòàòû ñòàòüè îõâàòûâàþò âñå ðàçíîâèä-
íîñòè ÀÎÃ-ìîäåëåé, òàê êàê áàçèðóþòñÿ òîëüêî íà îáùèõ ñâîéñòâàõ ýòèõ
ìîäåëåé — àöèêëè÷íîñòè îðãðàôà è êðèòåðèè d-ñåïàðàöèè.
ÀÎÃ-ìîäåëè — íàãëÿäíûé è êîìïàêòíûé ÿçûê ïðåäñòàâëåíèÿ ñèñòåì çàâè-
ñèìîñòåé [1–7]. Îíè ÿâëÿþòñÿ ýôôåêòèâíûì àïïàðàòîì îòîáðàæåíèÿ ñâÿçåé
(âïëîòü äî ïðè÷èííî-ñëåäñòâåííûõ îòíîøåíèé) è èíñòðóìåíòîì âåðîÿòíîñòíûõ
ðàññóæäåíèé îò ñâèäåòåëüñòâ (â ýêñïåðòíûõ ñèñòåìàõ). Ýòè ñâîéñòâà äåëàþò
ÀÎÃ-ìîäåëè ñðåäñòâîì ðåøåíèÿ ðàçíîîáðàçíûõ çàäà÷: ìåäèöèíñêàÿ è òåõíè÷åñ-
êàÿ äèàãíîñòèêà, ðàñïîçíàâàíèå ðå÷è, ïðîãíîçèðîâàíèå ïîñëåäñòâèé ðåøåíèé è
äåéñòâèé, àíàëèç äàííûõ â ýêîíîìåòðèêå, ñîöèîìåòðèêå, ìèêðîáèîëîãèè è ò.ä.
[3–5, 8]. Äëÿ ðåøåíèÿ ðàçíûõ ïîçíàâàòåëüíûõ, èññëåäîâàòåëüñêèõ è ïðîãíîç-
íî-àíàëèòè÷åñêèõ çàäà÷ íåîáõîäèìî âûâîäèòü ñòðóêòóðó ìîäåëè íà îñíîâå âû-
áîðêè äàííûõ íàáëþäåíèé çà ìîäåëèðóåìîé ñèñòåìîé. Èçâåñòíî, ÷òî çàäà÷à âû-
âîäà ÀÎÃ-ìîäåëè èç äàííûõ â îáùåì ñëó÷àå — NP-ñëîæíàÿ [9]. Âû÷èñëèòåëü-
íûå ñëîæíîñòè ñòàíîâÿòñÿ ñåðüåçíîé ïðàêòè÷åñêîé ïðîáëåìîé, êîãäà ÷èñëî
ïåðåìåííûõ ìîäåëè äîñòèãàåò íåñêîëüêèõ äåñÿòêîâ. Ïîìèìî òîãî, ñóùåñòâóåò
ïðîáëåìà íàäåæíîñòè âûâîäà ìîäåëè. Ïîýòîìó íà ïðàêòèêå ÷àñòî ïðèõîäèòñÿ
ïîëàãàòüñÿ íà àïðèîðíûå çíàíèÿ èëè ïðèíèìàòü æåñòêèå ïðåäïîëîæåíèÿ è (èëè)
âûíóæäåííûå îãðàíè÷åíèÿ, òåì ñàìûì ñíèæàÿ öåííîñòü âûâîäà.
Ïðîáëåìà ïîèñêà è ïîäáîðà ñåïàðàòîðîâ â ìîäåëÿõ çàâèñèìîñòåé âîçíèêàåò
â ðàçëè÷íûõ âèäàõ çàäà÷, è ïðåæäå âñåãî — ïðè âûâîäå ÀÎÃ-ìîäåëè èç äàííûõ
ìåòîäàìè òàê íàçûâàåìîãî constraint-based («ñåïàðàöèîííîãî») ïîäõîäà
[2, 3, 5, 7]. Ïîèñê ñåïàðàòîðîâ â ñëîæíûõ ñòðóêòóðàõ — êîìáèíàòîðíàÿ çàäà÷à.
Âàæíî êàê ìîæíî ðàíüøå ðàñïîçíàòü ñèòóàöèþ, êîãäà ïðåäïîëàãàåìîãî ñåïàðà-
òîðà íå ñóùåñòâóåò, è ïðåêðàòèòü áåñïåðñïåêòèâíûé ïîèñê. Îò ñîñòàâà ñåïàðàòî-
ðà çàâèñèò îáúåì âû÷èñëåíèé è íàäåæíîñòü òåñòîâ íåçàâèñèìîñòè, ïîýòîìó æå-
ëàòåëüíî íàõîäèòü ìèíèìàëüíûå ñåïàðàòîðû. Ìèíèìèçàöèÿ ñåïàðàòîðîâ òàêæå
èìååò çíà÷åíèå â çàäà÷àõ ðàññóæäåíèé ñ èñïîëüçîâàíèåì ìîäåëè (ïðè âûâîäå
ñëåäñòâèé èç ñâèäåòåëüñòâ), òàê êàê èíôîðìàöèÿ ðàñïðîñòðàíÿåòñÿ ïî ñòðóêòóðå
ìîäåëè ÷åðåç ñåïàðàòîðû. Ñôîðìóëèðîâàâ òðåáîâàíèÿ ê ýëåìåíòàì ñåïàðàòîðîâ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 17
© À.Ñ. Áàëàáàíîâ, 2008
ìîæíî îòñåÿòü íåêîòîðûå êàíäèäàòû â ñåïàðàòîð è òåì ñàìûì óïðîñòèòü çàäà÷ó.
 ðàáîòå ïîêàçàíû íîâûå âîçìîæíîñòè â ïîèñêå è ïîäáîðå ñåïàðàòîðîâ â ÀÎÃ-
ìîäåëÿõ, ÷òî äîëæíî îáåñïå÷èòü ïîâûøåíèå ýôôåêòèâíîñòè ðåøåíèÿ
ñîîòâåòñòâóþùèõ çàäà÷ âûâîäà. Äëÿ ðàçâåðíóòîé õàðàêòåðèñòèêè ïðîáëåìû
òðåáóåòñÿ î÷åðòèòü òåîðåòè÷åñêèå îñíîâû ÀÎÃ-ìîäåëåé çàâèñèìîñòåé.
ÎÑÍÎÂÛ ÒÅÎÐÈÈ ÀÎÃ-ÌÎÄÅËÅÉ ÇÀÂÈÑÈÌÎÑÒÅÉ. ÑÅÏÀÐÀÖÈß. ÏÐÎÁËÅÌÀ
Âåðîÿòíîñòíûå ìîäåëè çàâèñèìîñòåé íà îñíîâå ãðàôîâ — àêòóàëüíàÿ òåìà ñîâðå-
ìåííûõ èññëåäîâàíèé íà ñòûêå ìíîãîìåðíîãî ñòàòèñòè÷åñêîãî àíàëèçà, òåîðèè
ãðàôîâ, òåîðèè èíôîðìàöèè è èñêóññòâåííîãî èíòåëëåêòà. Âåðîÿòíîñòíûå ãðàôî-
âûå ìîäåëè çàâèñèìîñòåé — ñòðîãèé ÿçûê ïðåäñòàâëåíèÿ çíàíèé â óñëîâèÿõ íå-
ïîëíîòû è íåîïðåäåëåííîñòè. Íàèáîëåå ïîïóëÿðíû ÀÎÃ-ìîäåëè. Ê äîñòîèíñòâàì
ÀÎÃ-ìîäåëåé îòíîñÿòñÿ íàãëÿäíîñòü, ñïîñîáíîñòü îòîáðàæàòü ïðè÷èííî-ñëå-
äñòâåííûå ñâÿçè, êîìïàêòíîå (ïî ÷èñëó ïàðàìåòðîâ) ïðåäñòàâëåíèå ñèñòåì çàâè-
ñèìîñòåé è âû÷èñëèòåëüíàÿ ýôôåêòèâíîñòü âåðîÿòíîñòíîãî âûâîäà îò ñâèäå-
òåëüñòâ [1–4]. Âåðîÿòíîñòíûå ãðàôîâûå ìîäåëè çàâèñèìîñòåé ìîæíî èäåíòèôèöè-
ðîâàòü èíäóêòèâíî, íà îñíîâå ñòàòèñòè÷åñêèõ äàííûõ (îïèðàÿñü íà íåñêîëüêî
ìåòîäîëîãè÷åñêèõ ïîñòóëàòîâ). Òàêèì îáðàçîì, ýòî îäèí èç ïîäõîäîâ ê îòêðûòèþ
çíàíèé â áàçàõ äàííûõ.
Çàôèêñèðóåì ýëåìåíòàðíûå ãðàôîâûå ïîíÿòèÿ. Åñëè â îðãðàôå G åñòü äóãà
x y� , òî âåðøèíà x íàçûâàåòñÿ «ðîäèòåëåì» âåðøèíû y, à âåðøèíà y — ðåáåí-
êîì âåðøèíû x. Ðåáðî — ýòî äóãà, îðèåíòàöèÿ êîòîðîé íåèçâåñòíà èëè èãíîðè-
ðóåòñÿ. Âåðøèíû x è y íàçûâàþòñÿ ñìåæíûìè, åñëè îíè ñîåäèíåíû ðåáðîì, ÷òî
îáîçíà÷àåòñÿ êàê x y— . Îòñóòñòâèå ðåáðà áóäåì îáîçíà÷àòü êàê � ( — )x y . Ïóòü
â îðãðàôå — ïîñëåäîâàòåëüíîñòü ñìåæíûõ ðåáåð (ò.å. äóã ëþáîé îðèåíòàöèè),
áåç ïîâòîðåíèÿ âåðøèí. Êàê èñêëþ÷åíèå, ïåðâàÿ è ïîñëåäíÿÿ âåðøèíû ïóòè ìî-
ãóò ñîâïàäàòü, è òîãäà ýòîò ïóòü íàçûâàþò öèêëîì. Îðïóòü (ñòðîãî îðèåíòèðî-
âàííûé ïóòü) — ïóòü, íà êîòîðîì âñå ðåáðà îðèåíòèðîâàíû â íàïðàâëåíèè îäíî-
ãî è òîãî æå êîíöà ïóòè. Àöèêëè÷åñêèé îðèåíòèðîâàííûé ãðàô (ÀÎÃ) — îðãðàô,
â êîòîðîì íåò îðèåíòèðîâàííûõ öèêëîâ. Ââèäó àöèêëè÷íîñòè ëþáîé ÀÎà ñîäåð-
æèò êîðíè (êîðåíü). Äàëåå ïîä îðãðàôîì áóäåì ïîäðàçóìåâàòü ÀÎÃ. Åñëè â ãðà-
ôå åñòü îðïóòü x y� �� � � , òî âåðøèíà x íàçûâàåòñÿ ïðåäêîì âåðøèíû y.
ÀÎÃ-ìîäåëü — ýòî ìîäåëü, ñòðóêòóðà êîòîðîé — îðãðàô áåç îðöèêëîâ
(è ïåòåëü), ïðè÷åì êàæäîé ïåðåìåííîé ñîîòâåòñòâóåò âåðøèíà ãðàôà. ÀÎÃ-ìîäåëü
îïðåäåëÿåòñÿ êàê ( , )G � , ãäå G — ÀÎÃ, à � — ñîâîêóïíîñòü ëîêàëüíî çàäàííûõ ïà-
ðàìåòðîâ. Áîëåå èçâåñòíû äâà âèäà ÀÎÃ-ìîäåëåé: áàéåñîâñêèå ñåòè è ãàóññîâû ñåòè.
(Çàìåòèì, ÷òî íàèìåíîâàíèå «áàéåñîâñêèå ñåòè» øèðîêî èñïîëüçóåòñÿ ïî îòíîøå-
íèþ êî âñåì ÀÎÃ-ìîäåëÿì.) Íå áóäåì ðàçëè÷àòü ðàçíîâèäíîñòè ÀÎÃ-ìîäåëåé, òàê
êàê ýêñïëóàòèðóåì òîëüêî ãðàôîâûå ñâîéñòâà ìîäåëåé (íå ïàðàìåòðè÷åñêèå). (Ëè-
íåéíîñòü ìîäåëè îáëåã÷àåò àíàëèç è ïðåäîòâðàùàåò íåêîòîðûå îñëîæíåíèÿ.) Ïðåä-
ëàãàåìûå ñðåäñòâà áîëåå âàæíû äëÿ áàéåñîâñêèõ ñåòåé, ïîñêîëüêó äëÿ íèõ ñëîæíåå
âû÷èñëÿòü ñòàòèñòèêè äëÿ òåñòîâ. Ââèäó âçàèìíî îäíîçíà÷íîãî ñîîòâåòñòâèÿ
òåðìèíû «ïåðåìåííàÿ» (ìîäåëè) è «âåðøèíà» (ãðàôà) â ëèòåðàòóðå óïîòðåáëÿþòñÿ
êàê âçàèìîçàìåíÿåìûå.
Îïðåäåëåíèå 1.Êîëëàéäåðîì (êîëëèçîðîì) â ãðàôå íàçûâàåòñÿ ôðàãìåíò
âèäà x y z� � . Åñëè êîëëàéäåð x y z� � ÿâëÿåòñÿ ÷àñòüþ ïóòè � â îðãðàôå, òî
y íàçûâàåòñÿ êîëëàéäåðíîé âåðøèíîé íà ïóòè �. (Ïðè ýòî âåðøèíà y ìîæåò áûòü
íåêîëëàéäåðíîé íà íåêîòîðîì äðóãîì ïóòè.)
Áåñêîëëàéäåðíûé (áåñêîëëèçîðíûé) ïóòü, èëè öåïü, â îðãðàôå — ïóòü, íå
ñîäåðæàùèé íè îäíîãî êîëëàéäåðà.
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Îòíîøåíèå ìåæäó ñòðóêòóðîé ìîäåëè è ôàêòàìè óñëîâíîé íåçàâèñèìîñòè,
ïðåäñòàâëåííûìè â ÀÎÃ-ìîäåëè, ôîðìàëèçîâàíî ñ ïîìîùüþ êðèòåðèÿ d-ñåïàðà-
öèè [1, 3, 4, 6]. Ïåðåä ôîðìóëèðîâêîé îïðåäåëåíèÿ d-ñåïàðàöèè öåëåñîîáðàçíî
äàòü ïîÿñíåíèÿ. Â îðèãèíàëå îïðåäåëåíèÿ èñïîëüçóåòñÿ ïðîñòàÿ êîíñòðóêöèÿ
«given S» (ãäå S — ìíîæåñòâî âåðøèí). Áóêâàëüíûé ïåðåâîä, î÷åâèäíî, íå ãîäèò-
ñÿ. Ïî ñìûñëó ìîæíî áûëî áû ñêàçàòü «ïðè áëîêèðîâàíèè S» èëè «ïðè ôèêñàöèè
ñîñòîÿíèÿ ìíîæåñòâà âåðøèí S». Îäíàêî ñëîâî «áëîêèðîâàíèå» ïðèíÿòî óïîò-
ðåáëÿòü ïî îòíîøåíèþ ê ïóòÿì (íå âåðøèíàì). Âòîðîé âàðèàíò ïåðåâîäà — ãðî-
ìîçäêèé, ê òîìó æå ïîòðåáóåò îïðåäåëèòü, ÷òî òàêîå «ñîñòîÿíèå âåðøèíû» è
«ôèêñàöèÿ». (Âïðî÷åì, ñïåöèàëèñòû ìîãóò ìûñëèòü èìåííî òàêèìè ïîíÿòèÿìè.)
Ïîýòîìó ïðåäëàãàåì èñïîëüçîâàòü ñëîâî «êîíäèöèîíèðîâàíèå» (ò.å. ââåäåíèå â
óñëîâèå). Ýòîé îïåðàöèè íà ãðàôå ñîîòâåòñòâóåò îäíîèìåííàÿ îïåðàöèÿ íàä äàí-
íûìè (èëè íàä ðàñïðåäåëåíèåì âåðîÿòíîñòåé). Êîãäà ïî êîíòåêñòó ðîëü
ìíîæåñòâà S ïîíÿòíà, ìîæíî îáîéòèñü áåç óòî÷íÿþùåãî òåðìèíà, à ïðîñòî
ñêàçàòü «ñ ïîìîùüþ ìíîæåñòâà âåðøèí S».
Îïðåäåëåíèå 2 (d-ñåïàðàöèÿ). Ïóòü � â ÀÎÃ-ìîäåëè íàçûâàþò d-çàêðûòûì
(d-áëîêèðîâàííûì) ñ ïîìîùüþ (êîíäèöèîíèðîâàíèÿ) ìíîæåñòâà âåðøèí S, åñëè è
òîëüêî åñëè âûïîëíÿåòñÿ õîòÿ áû îäíî èç ñëåäóþùèõ óñëîâèé:
1) ñóùåñòâóåò âåðøèíà x, x �S, x ��, ïðè÷åì íà ïóòè � åñòü äóãà x � èëè
� x;
2) íà ïóòè � åñòü õîòÿ áû îäèí êîëëàéäåð � �y , ïðè÷åì y �S è âåðøèíà y
íå ÿâëÿåòñÿ ïðåäêîì íèêàêîé âåðøèíû â S, ò.å. íå ñóùåñòâóåò íèêàêîé z �S, òà-
êîé, ÷òî åñòü y z� �� � � .
Ìíîæåñòâî âåðøèí S d-ñåïàðèðóåò âåðøèíû x è y, åñëè è òîëüêî åñëè âñå
ïóòè ìåæäó x è y ÿâëÿþòñÿ d-çàêðûòûìè ñ ïîìîùüþ ìíîæåñòâà âåðøèí S. Áóäåì
îáîçíà÷àòü òàêóþ d-ñåïàðàöèþ ïðåäèêàòîì Ds ( )x y� �S . Êîãäà S
, áóäåì
ïèñàòü Ds ( )x y� � . Åñëè õîòÿ áû îäèí ïóòü ìåæäó x è y íå ÿâëÿåòñÿ d-çàêðû-
òûì, òî ãîâîðÿò, ÷òî âåðøèíû x è y d-ñîåäèíåíû. Ýòî îáîçíà÷àåòñÿ
� � �Ds ( )x yS .
Îïðåäåëåíèå 3 (ñåïàðàòîð). Åñëè â ÀÎÃ ïðåäèêàò Ds ( )x y� �S èñòèíåí, òî
ìíîæåñòâî âåðøèí S íàçûâàþò (ãðàôîâûì) ñåïàðàòîðîì äëÿ ïàðû ( , )x y .
Ïîíÿòèå ñåïàðàòîðà åñòåñòâåííûì îáðàçîì ðàñøèðÿåòñÿ íà ñëó÷àé
Ds ( )X S Y� � , ãäå X è Y — ìíîæåñòâà âåðøèí. Î÷åâèäíî, â ëþáîé ãðàôîâîé
ìîäåëè (äàæå áîëåå îáùåé, ÷åì ÀÎÃ) èç ñóùåñòâîâàíèÿ ðåáðà x y— ñëåäóåò îò-
ñóòñòâèå ñåïàðàòîðà äëÿ ( , )x y . Îáðàòíàÿ èìïëèêàöèÿ âåðíà òîëüêî äëÿ ÀÎÃ, ò.å.
â ìîäåëÿõ áåç ñêðûòûõ ïåðåìåííûõ.
Öåëü àíàëèòèêà ïðè ðåøåíèè ìíîãèõ ïîçíàâàòåëüíûõ è èññëåäîâàòåëüñêèõ
ïðîáëåì — âûâåñòè ñòðóêòóðó ìîäåëè èç ñòàòèñòè÷åñêèõ äàííûõ íàáëþäåíèé çà
ìîäåëèðóåìîé ñèñòåìîé. Ýòà çàäà÷à ñâîäèòñÿ ê èäåíòèôèêàöèè âñåõ äóã ãðàôà
ìîäåëè. Íàëè÷èå èëè îòñóòñòâèå ðåáåð ñëåäóåò âåðèôèöèðîâàòü íà îñíîâå ñîîò-
âåòñòâóþùèõ ñòàòèñòè÷åñêèõ ñâîéñòâ ýìïèðè÷åñêèõ äàííûõ, à èìåííî, ôàêòîâ
óñëîâíîé íåçàâèñèìîñòè. Óñëîâíóþ íåçàâèñèìîñòü ïåðåìåííîé x îò ïåðåìåííîé
y ïðè êîíäèöèîíèðîâàíèè ìíîæåñòâà ïåðåìåííûõ S îáîçíà÷èì Pr ( )x y� �S .
Ïðè ýòîì ïîäðàçóìåâàåòñÿ, ÷òî x y, �S. Äëÿ äèñêðåòíûõ ïåðåìåííûõ ýòà óñëîâ-
íàÿ íåçàâèñèìîñòü îçíà÷àåò p y x p y( | , ) ( | )S S .  ëèíåéíûõ ìîäåëÿõ óñëîâíàÿ
íåçàâèñèìîñòü ïðîÿâëÿåòñÿ êàê íóëåâîå (â êîíå÷íîé âûáîðêå — íåçíà÷èìî îòëè-
÷àþùååñÿ îò íóëÿ) çíà÷åíèå êîýôôèöèåíòà ÷àñòíîé êîððåëÿöèè. Áåçóñëîâíóþ
íåçàâèñèìîñòü, íàïðèìåð Pr ( )x y�
� , çàïèøåì â ôîðìå Pr ( )x y�� . Ôàêò áå-
çóñëîâíîé çàâèñèìîñòè îáîçíà÷èì � ��Pr ( )x y . (Íàïîìíèì, ÷òî â êîíå÷íîé
âûáîðêå íå âñÿêèå çàâèñèìîñòè ñòàòèñòè÷åñêè çíà÷èìû.)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 19
Áîëüøèíñòâî èçâåñòíûõ ìåòîäîâ âûâîäà ñòðóêòóðû ìîäåëè èç ñòàòèñòè÷åñ-
êèõ äàííûõ îòíîñÿòñÿ ëèáî ê îïòèìèçàöèîííîìó, ëèáî ê «ñåïàðàöèîííîìó»
(constraint-based) ïîäõîäó [2, 3, 5, 7]. Ïîñëåäíèé îñíîâàí íà âûÿâëåíèè ôàêòîâ
óñëîâíîé íåçàâèñèìîñòè.
Èçâåñòíî [6], ÷òî èç d-ñåïàðàöèè ñëåäóåò èñòèííîñòü ñîîòâåòñòâóþùåãî
óòâåðæäåíèÿ óñëîâíîé íåçàâèñèìîñòè, ò.å.
Ds Pr( ) ( )x y x y� � � � �S S . (1)
Òàêèì îáðàçîì, êðèòåðèé d-ñåïàðàöèè îáåñïå÷èâàåò ñ÷èòûâàíèå óòâåðæäåíèé
óñëîâíîé íåçàâèñèìîñòè èç ãðàôà ÀÎÃ-ìîäåëè. Îäíàêî äëÿ âûâîäà ìîäåëè èç
äàííûõ íóæíû ïðàâèëà îáðàòíîãî âèäà.
Îñíîâíûì ìåòîäîëîãè÷åñêèì ïîñòóëàòîì ñåïàðàöèîííûõ ìåòîäîâ ÿâëÿåòñÿ
ïðåäïîëîæåíèå íåîáìàí÷èâîñòè (faithfulness) ðàñïðåäåëåíèÿ âåðîÿòíîñòåé
ÀÎÃ-ìîäåëè [2, 3, 7, 10], êîòîðîå ìîæíî âûðàçèòü êàê
Pr Ds( ) ( )x y x y� � � � �S S , (2)
ò.å. êàê îáðàòíóþ èìïëèêàöèþ ïî ñðàâíåíèþ ñ (1). Ñîïîñòàâëÿÿ (1) è (2), ïî-
ëó÷àåì
Ds Pr( ) ( )x y x y� � � � �S S . (3)
Òàêèì îáðàçîì, âûïîëíåíèå (2) îáåñïå÷èâàåò ñòðóêòóðíî-ïîâåäåí÷åñêèé èçî-
ìîðôèçì ìîäåëè.
Ñîïîñòàâëÿÿ ñâîéñòâî ÀÎÃ-ìîäåëåé ( — ) : ( )x y x y� �
� �S SDs è ýêâè-
âàëåíòíîñòü (3), ïîëó÷àåì
x y x y— : ( )� �
� �S SPr . (4)
Ïðèíöèï (4) ëåæèò â îñíîâå áîëüøèíñòâà ñåïàðàöèîííûõ ìåòîäîâ, â ÷àñ-
òíîñòè àëãîðèòìà PC [2, 3, 5]. Çàìåòèì, ÷òî (4) îïèðàåòñÿ íà îñëàáëåííóþ ôîðìó
ïðåäïîëîæåíèÿ íåîáìàí÷èâîñòè (êîòîðàÿ õàðàêòåðèçóåò òîëüêî ðåáðà, à íå ëþ-
áûå ïóòè), íî ýòîãî äîñòàòî÷íî äëÿ ïîñòðîåíèÿ ðåçóëüòàòèâíîãî àëãîðèòìà èäåí-
òèôèêàöèè âñåõ ðåáåð ìîäåëè. Îäíàêî äàæå òàêàÿ îñëàáëåííàÿ ôîðìà ïðåäïîëî-
æåíèÿ íåîáìàí÷èâîñòè ìîæåò èçðåäêà íàðóøàòüñÿ, ÷òî ñîçäàåò ðèñê îøèáêè.
Îïðåäåëåíèå 4[11, 12]. Ëîêàëüíî-ìèíèìàëüíûì ñåïàðàòîðîì äëÿ ïàðû âåð-
øèí ( , )x y â ÀÎÃ íàçûâàåòñÿ òàêîé ñåïàðàòîð S, ÷òî ïîñëå óäàëåíèÿ èç S ëþáîãî
åãî ÷ëåíà (ýëåìåíòà) îí ïåðåñòàåò áûòü ñåïàðàòîðîì äëÿ ( , )x y . Ôîðìàëüíî ýòî
çàïèñûâàåòñÿ êàê
Ds Ds { }( ) & : ( \ )x y z x z y� � � � � � �S S S .
Îïðåäåëåíèå 5 [12]. Íàçîâåì ñåïàðàòîð S* äëÿ ïàðû âåðøèí ( , )x y â ÀÎÃ
ìèíèìàëüíûì ñåïàðàòîðîì, åñëè äëÿ ( , )x y íå ñóùåñòâóåò ñåïàðàòîðà ìåíüøåé
êàðäèíàëüíîñòè, ò.å. äëÿ âñåõ äðóãèõ ñåïàðàòîðîâ S äëÿ ïàðû ( , )x y âåðíî
| | | |*S S� .
Îáîçíà÷èì ìèíèìàëüíûé è ëîêàëüíî-ìèíèìàëüíûé ñåïàðàòîð äëÿ ïàðû âåð-
øèí ( , )x y ñîîòâåòñòâåííî S x ymin ( , ) è S x ylom ( , ).
Ïðè àíàëèçå ñâîéñòâ ñåïàðàöèè â ÀÎÃ-ìîäåëÿõ áóäåì îïèðàòüñÿ òîëüêî íà
êðèòåðèé d-ñåïàðàöèè è çàïðåò îðöèêëîâ. Â ýòîì àíàëèçå íåëüçÿ âîñïîëüçîâàòüñÿ
èçâåñòíûìè ìåòîäàìè è ðåçóëüòàòàìè òåîðèè ãðàôîâ (è òðàíñïîðòíûõ çàäà÷)
ââèäó ñëåäóþùèõ îñîáåííîñòåé:
1) çàâèñèìîñòè áëîêèðóþòñÿ ìàíèïóëÿöèåé âåðøèí (ïåðåìåííûõ), à íå ðå-
áåð;
2) ñâîéñòâà d-ñåïàðàöèè ñóùåñòâåííî îòëè÷àþòñÿ îò òðàíñïîðòíûõ àíàëî-
ãîâ;
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
3) îáû÷íî â ìîìåíò ïîèñêà ñåïàðàòîðà ñòðóêòóðà ãðàôà åùå íåèçâåñòíà (èç-
âåñòíû òîëüêî íåêîòîðûå ôàêòû è îãðàíè÷åíèÿ).
 ÀÎÃ-ìîäåëÿõ ðåáðà ñîîòâåòñòâóþò àññîöèàöèÿì (çàâèñèìîñòÿì). Áëîêèðî-
âàòü ñàìè ðåáðà àíàëèòèê íå ìîæåò. Íèêàêèå îïåðàöèè âðîäå ïîèñêà ðàçðåçà ãðàôà
íåäîñòóïíû. Ïðè àíàëèçå äàííûõ (ðàñïðåäåëåíèé âåðîÿòíîñòåé) äîñòóïíû
òîëüêî îïåðàöèè ñ ïåðåìåííûìè. Ñëåäóåò îòìåòèòü è áîëåå òîíêîå îòëè÷èå d-ñå-
ïàðàöèè îò áëîêèðîâàíèÿ ïîòîêîâ â òðàíñïîðòíûõ ñåòÿõ. Ñîãëàñíî îïðåäåëå-
íèþ 2 (óñëîâèå 2) âîçìîæíî ðàçáëîêèðîâàíèå ïóòè «ñáîêó», «èçäàëè». Ìåõàíè÷åñ-
êèé àíàëîã ýòîãî ÿâëåíèÿ íåèçâåñòåí (íàïðèìåð, àíàëîãèÿ ñ ñåìàôîðîì — íåòî÷íà).
 [13] ýòî îïèñàíî êàê ïðîâîöèðîâàíèå çàâèñèìîñòè. Ìîæíî èíòóèòèâíî ïðåäñòà-
âèòü, ÷òî â ìîäåëÿõ çàâèñèìîñòåé ïóòè ïðåäñòàâëÿþò «ïîòîêè âëèÿíèÿ» ëèáî «öåíû
äîñòàâêè», îäíàêî ýòè ñóððîãàòíûå ïîíÿòèÿ íå áóäóò ïîä÷èíÿòüñÿ íè îãðàíè÷åíèÿì
àääèòèâíîñòè öåíû, íè áàëàíñà «äåáåò-êðåäèò». (Êàê èñêëþ÷åíèå — â ëèíåéíûõ
ìîäåëÿõ âûïîëíÿåòñÿ àääèòèâíîñòü âëèÿíèé ÷åðåç ïàðàëëåëüíûå ïóòè.)
Îïðåäåëåíèå 6 (ýìïèðè÷åñêèé ñåïàðàòîð). Åñëè â (âûáîðî÷íîì) ðàñïðåäå-
ëåíèè âåðîÿòíîñòåé âûïîëíÿåòñÿ Pr ( )x y� �S , òî ìíîæåñòâî ïåðåìåííûõ S íà-
çûâàþò ýìïèðè÷åñêèì, èëè ñòàòèñòè÷åñêèì, ñåïàðàòîðîì äëÿ ïàðû ( , )x y .
Ýìïèðè÷åñêèé ñåïàðàòîð äëÿ ïàðû ( , )x y ìîæåò íå ñîâïàäàòü íè ñ îäíèì ãðà-
ôîâûì ñåïàðàòîðîì äëÿ ( , )x y â ìîäåëè, ÷òî îçíà÷àåò íàðóøåíèå ïðåäïîëîæåíèÿ
íåîáìàí÷èâîñòè. Ñàìûé õóäøèé ñëó÷àé — êîãäà ñóùåñòâóåò ðåáðî x y— è, òåì
íå ìåíåå, ñóùåñòâóåò ýìïèðè÷åñêèé ñåïàðàòîð äëÿ ( , )x y . Òîãäà ïðèíöèï (4)
äîïóñêàåò ñáîé.
Îäíèì èç íåäîñòàòêîâ ìåòîäîâ ñåïàðàöèîííîãî ïîäõîäà ÿâëÿåòñÿ íåíàäåæ-
íîñòü èäåíòèôèêàöèè ðåáåð ìîäåëè (ðèñê îøèáîê). Ýòîò ðèñê â îñíîâíîì îáúÿñ-
íÿåòñÿ íåíàäåæíîñòüþ ðåçóëüòàòîâ òåñòèðîâàíèÿ óòâåðæäåíèé óñëîâíîé íåçàâè-
ñèìîñòè, êîãäà àíàëèòèê ðàñïîëàãàåò âûáîðêîé äàííûõ íåäîñòàòî÷íî áîëüøîãî
îáúåìà. Äðóãàÿ ïðîáëåìà — íåóäîâëåòâîðèòåëüíàÿ âû÷èñëèòåëüíàÿ ýôôåêòèâ-
íîñòü ïîèñêà ñåïàðàòîðîâ. Âû÷èñëèòåëüíàÿ ýôôåêòèâíîñòü îïðåäåëÿåòñÿ
êîëè÷åñòâîì âûïîëíÿåìûõ òåñòîâ è èõ ñëîæíîñòüþ (ò.å. îáúåìîì âû÷èñëåíèÿ
íåîáõîäèìûõ ñòàòèñòèê.)
Çàäà÷à ïîèñêà ñåïàðàòîðîâ ïðè âûâîäå ñòðóêòóðû ÀÎÃ-ìîäåëè èç äàííûõ
ÿâëÿåòñÿ ïåðåáîðíîé, è ÷åì áîëüøå èìååòñÿ êàíäèäàòîâ â ñåïàðàòîð, òåì ñëîæ-
íåå ïîèñê. Äëÿ îïòèìèçàöèè ïîèñêà ñåïàðàòîðîâ àëãîðèòì PC îãðàíè÷èâàåò ìíî-
æåñòâî êàíäèäàòîâ â ÷ëåíû ñåïàðàòîðà äëÿ ( , )x y ìíîæåñòâîì âåðøèí, êîòîðûå
ñ÷èòàþòñÿ ñìåæíûìè ñ x èëè y íà äàííîì ýòàïå âûâîäà ìîäåëè. Òàêàÿ òàêòèêà
îáåñïå÷èâàåò êîððåêòíûé âûâîä ïðè óñëîâèè âûïîëíåíèÿ (4). Îäíàêî îíà íåñî-
âåðøåííà â òîì, ÷òî àëãîðèòì: 1) íå âñåãäà íàõîäèò ìèíèìàëüíûå ñåïàðàòîðû; 2)
ïðîäîëæàåò èñêàòü ñåïàðàòîð äî ïîëíîãî èñ÷åðïàíèÿ âàðèàíòîâ äàæå òîãäà, êîã-
äà ñåïàðàòîðà íå ñóùåñòâóåò. Âñëåäñòâèå ýòîãî àëãîðèòì ðèñêóåò äîïóñòèòü
îøèáêó ïðè òåñòèðîâàíèè óñëîâíîé íåçàâèñèìîñòè ñ áîëüøîé êàðäèíàëüíîñòüþ
óñëîâèÿ.
Ïîðÿäîê (ðàíã) òåñòà óñëîâíîé íåçàâèñèìîñòè Pr ( )x y� �S îïðåäåëÿåòñÿ
êàðäèíàëüíîñòüþ óñëîâèÿ S. Ñ ðîñòîì êàðäèíàëüíîñòè S ïðîèñõîäèò, ïî ñóùåñ-
òâó, äðîáëåíèå âûáîðêè äàííûõ. Ôàêòîð äðîáëåíèÿ âûáîðêè (â äèñêðåò-
íûõ ìîäåëÿõ) èìååò ïîðÿäîê âåëè÷èíû | | | | | | | | | | | |x y� � S , ãäå | | | | | | | |S � i iz , zi �S,
| | | |x — çíà÷íîñòü (àðíîñòü) ïåðåìåííîé x. Ýòîò æå ôàêòîð îöåíèâàåò îáúåì
âû÷èñëåíèÿ ñòàòèñòèê, íåîáõîäèìûõ äëÿ òåñòà.
Òàêèì îáðàçîì, äëÿ íàäåæíîãî è ýôôåêòèâíîãî âîññòàíîâëåíèÿ «èñòèííîé»
ñòðóêòóðû ìîäåëè íåîáõîäèìî ïî âîçìîæíîñòè îáõîäèòüñÿ òåñòàìè íèçêîãî ïî-
ðÿäêà. Îòñþäà âûòåêàåò çíà÷åíèå è âàæíîñòü çàäà÷è ïîèñêà ìèíèìàëüíûõ ñåïàðàòî-
ðîâ è çàäà÷à áûñòðîãî ðàñïîçíàâàíèÿ ñèòóàöèè, êîãäà ñåïàðàòîðà íå ñóùåñòâóåò.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 21
Êëþ÷åâàÿ èäåÿ ïðåäëàãàåìîãî àíàëèçà — èñïîëüçîâàòü çíàíèÿ îá îäíèõ ñå-
ïàðàòîðàõ è çàâèñèìîñòÿõ äëÿ õàðàêòåðèñòèêè äðóãèõ ñåïàðàòîðîâ è ñâÿçåé.
Åñòåñòâåííî, â êà÷åñòâå ïðèçíàêîâ ñëåäóåò èñïîëüçîâàòü ìåíåå ñëîæíûå êî-
íñòðóêöèè (óñëîâèÿ), ÷åì â ðåçîëþöèîííîé ÷àñòè óòâåðæäåíèé è ïðàâèë. Íåêî-
òîðûå âîçìîæíîñòè â ýòîì íàïðàâëåíèè (íà áàçå áåçóñëîâíûõ çàâèñèìîñòåé, ñ
èñïîëüçîâàíèåì ïîíÿòèÿ ãåíîòèïîâ ïåðåìåííûõ) ïîêàçàíû â [11]. Àïïàðàò ãåíî-
òèïîâ ïåðåìåííûõ ÿâëÿåòñÿ êîìïàêòíûì ñïîñîáîì ïðåäñòàâëåíèÿ ìíîæåñòâà
áåçóñëîâíûõ (íå)çàâèñèìîñòåé.  [12] ïîëó÷åíû íîâûå ðåçóëüòàòû; â äàííîé
ðàáîòå ïðåäëàãàåòñÿ èõ ðàçâèòèå.
ÑÂÎÉÑÒÂÀ ËÎÊÀËÜÍÎ-ÌÈÍÈÌÀËÜÍÛÕ ÑÅÏÀÐÀÒÎÐÎÂ
(È ÈÕ ÝËÅÌÅÍÒÎÂ) Â ÀÎÃ-ÌÎÄÅËßÕ
Î÷åâèäíî, ÷òî êàæäûé ìèíèìàëüíûé ñåïàðàòîð ÿâëÿåòñÿ òàêæå è ëîêàëü-
íî-ìèíèìàëüíûì. Çíà÷èò, âñå íåîáõîäèìûå òðåáîâàíèÿ ê ÷ëåíàì ëîêàëüíî-ìè-
íèìàëüíûõ ñåïàðàòîðîâ ïîëíîñòüþ ðàñïðîñòðàíÿþòñÿ íà ÷ëåíîâ ìèíèìàëüíûõ
ñåïàðàòîðîâ. Êîãäà ëîêàëüíî-ìèíèìàëüíûé ñåïàðàòîð åäèíñòâåííûé, îí ìèíè-
ìàëåí. Â îäíîì è òîì æå ÀÎÃ ìîæåò áûòü íåñêîëüêî ìèíèìàëüíûõ ñåïàðàòî-
ðîâ äëÿ ïàðû âåðøèí ( , )x y . Â òî æå âðåìÿ åäèíñòâåííûé S x ymin ( , ) ìîæåò íå
èìåòü íè îäíîãî îáùåãî ÷ëåíà ñ íåêîòîðûì S x ylom ( , ). Èçâåñòíî [14], ÷òî íè-
êàêîå ïîäìíîæåñòâî ìíîæåñòâà S x ylom ( , ) íå ìîæåò áûòü ñåïàðàòîðîì äëÿ
ïàðû âåðøèí ( , )x y . Òàêèì îáðàçîì, ëîêàëüíî-ìèíèìàëüíûå ñåïàðàòîðû
ÿâëÿþòñÿ «íåñæèìàåìûìè».
Íà÷íåì ñ êîíñòàòàöèè ýëåìåíòàðíûõ ñâîéñòâ.
Ôàêò 1. Åñëè â ãðàôå âåðíî Ds ( )x y� � , òî äëÿ ïàðû âåðøèí ( , )x y èìååòñÿ
òîëüêî îäèí ëîêàëüíî-ìèíèìàëüíûé ñåïàðàòîð, à èìåííî — ïóñòîé.
Ôàêò 2.Êàæäûé ÷ëåí êàæäîãî ëîêàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà S ÿâëÿåò-
ñÿ íåêîëëàéäåðíîé âåðøèíîé íà òîì ïóòè (ïóòÿõ), êîòîðûé îí áëîêèðóåò, ïðè-
÷åì ýòîò ïóòü (êàê ìèíèìóì îäèí èç ïóòåé) íå áëîêèðóåòñÿ íèêàêèì äðóãèì
÷ëåíîì S.
Ôàêò 3. Êàæäûé ÷ëåí x êàæäîãî ëîêàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà èìååò
íå ìåíåå îäíîé èñõîäÿùåé äóãè x � è íå ìåíåå äâóõ áåçóñëîâíî çàâèñèìûõ âåð-
øèí (ò.å. d-ñîåäèíåííûõ ñ x).
Ýòè ôàêòû ñëåäóþò ïðÿìî èç îïðåäåëåíèé 2 è
4. Çàìåòèì, ÷òî ôàêò 2 íåëüçÿ «ïðÿìîëèíåéíî» óñè-
ëèòü. À èìåííî, íåëüçÿ ïîòðåáîâàòü, ÷òîáû äëÿ êàæ-
äîé z S x y� lom ( , ) ñóùåñòâîâàë ïóòü ìåæäó âåðøè-
íàìè x è y ÷åðåç z, òàêîé, ÷òî îäíà èç äâóõ ÷àñòåé
ýòîãî ïóòè áûëà áû öåïüþ. (Òàêîå îøèáî÷íîå òðå-
áîâàíèå âõîäèò â ôîðìóëèðîâêó óòâåðæäåíèÿ, ïðåä-
ñòàâëåííîãî â [11].) Ïðèìåð íåâûïîëíåíèÿ ýòîãî
òðåáîâàíèÿ èëëþñòðèðóåòñÿ íà ðèñ. 1. Äëÿ äàííîé
ìîäåëè ìíîæåñòâî { }z r w, , ÿâëÿåòñÿ ìèíèìàëüíûì
ñåïàðàòîðîì äëÿ ( , )x y . Ëåãêî âèäåòü, ÷òî âåðøèíà w
íå ëåæèò íè íà êàêîé öåïè ìåæäó âåðøèíàìè x è y. Áîëåå òîãî, íåò íè îäíîãî
ïóòè ìåæäó âåðøèíàìè x è y ÷åðåç w, ÷àñòüþ êîòîðîãî áûëà áû öåïü x w— —���
èëè öåïü w y— —��� .
Ôàêò 4(ñòûêîâêà). Åñëè â ãðàôå åñòü õîòÿ áû îäíà öåïü z x— —��� è õîòÿ áû
îäèí îðïóòü x y� ��� � , òî ñóùåñòâóåò ïî êðàéíåé ìåðå îäíà öåïü ìåæäó z è y.
(Ïðè ýòîì äîïóñòèìî ïåðåñå÷åíèå íàçâàííûõ öåïè è îðïóòè.)
Èç ôàêòà 4 ëîãè÷åñêè âûòåêàåò ñëåäóþùåå.
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ðèñ. 1
Ôàêò 5(ïðàâèëî çàïðåòà äóãè):
� � � � � � � �w w y w x x y: ( ) & ( ) ( )Ds Ds ; (5)
� � � � � � � �z z x z y y x: ( ) & ( ) ( )Ds Ds . (5à)
Óòâåðæäåíèå 1 (ïðàâèëî íåïîãëîùåíèÿ). Åñëè â ÀÎÃ èìååì � � �Ds ( )x y
è ñóùåñòâóþò òàêèå âåðøèíû z è w, ÷òî Ds ( )z y� � , � � �Ds ( )z x , Ds ( )w x� �
è � � �Ds ( )w y , òî íåâîçìîæíî ðåáðî x y— , ò.å. ñóùåñòâóåò ñåïàðàòîð äëÿ
ïàðû âåðøèí ( , )x y .
Ïîíÿòíî, ÷òî êîãäà óñëîâèÿ âûïîëíåíû, âñå öåïè ìåæäó âåðøèíàìè x è y
èìåþò âèä x y� ��� � . Äðóãàÿ ôîðìà ýòèõ æå, ïî ñóòè, ïðàâèë äàíà â [11], ãäå
îíè âûðàæåíû ÷åðåç àïïàðàò ãåíîòèïîâ ïåðåìåííûõ.
Óòâåðæäåíèå 2. Â ñîñòàâå êàæäîãî íåïóñòîãî ëîêàëüíî-ìèíèìàëüíîãî ñåïà-
ðàòîðà äëÿ ïàðû âåðøèí ( , )x y åñòü, êàê ìèíèìóì, îäíà âåðøèíà, êîòîðàÿ ëåæèò
íà íåêîòîðîé öåïè ìåæäó âåðøèíàìè x è y.
Ýòà ôîðìóëèðîâêà ýêâèâàëåíòíà óòâåðæäåíèþ, äîêàçàííîìó â [12]. Óòâåðæäå-
íèå 2 íåëüçÿ óñèëèòü, â òîì ñìûñëå, ÷òî âîçìîæíû ñëó÷àè, êîãäà âñå ÷ëåíû ëîêàëü-
íî-ìèíèìàëüíîãî ñåïàðàòîðà, çà èñêëþ÷åíèåì îäíîãî, íå ëåæàò íè íà êàêèõ öåïÿõ
ìåæäó âåðøèíàìè x è y. Èëëþñòðàöèåé ñëóæèò ðèñ. 1.
Óòâåðæäåíèå 2a. Â ñîñòàâå êàæäîãî íåïóñòîãî ëîêàëüíî-ìèíèìàëüíîãî ñå-
ïàðàòîðà äëÿ ïàðû âåðøèí ( , )x y åñòü, êàê ìèíèìóì, îäíà âåðøèíà z òàêàÿ, ÷òî
� � � � � �Ds Ds( ) & ( )z x z y .
Ôàêò 6 (ïðàâèëî åäèíñòâåííîãî îáùåãî áëèçêîãî; single common covariate).
Åñëè â ÀÎÃ íåò ðåáðà x y— è � � �Ds ( )x y è åñòü òîëüêî îäíà âåðøèíà z, d-ñî-
åäèíåííàÿ ñ îáåèìè âåðøèíàìè x è y, òî âåðøèíà z âõîäèò â ñîñòàâ âñåõ ñåïàðà-
òîðîâ äëÿ ïàðû âåðøèí ( , )x y . Åñëè ïðè ýòèõ óñëîâèÿõ íåò íè îäíîé âåðøèíû w (
w x y� , ), d-ñîåäèíåííîé ñ âåðøèíîé z, òî {z} ÿâëÿåòñÿ åäèíñòâåííûì ëîêàëü-
íî-ìèíèìàëüíûì ñåïàðàòîðîì äëÿ ( , )x y .
Ôàêò 7. Ïóñòü â îðãðàôå íåò ðåáðà x y— , íî åñòü ïóòü x z y— — . Òîãäà
åñëè ýòîò ïóòü èìååò âèä x z y� � , òî íè âåðøèíà z, íè êàêîé-ëèáî åå ïîòîìîê
íå âõîäèò â ñîñòàâ íè îäíîãî ñåïàðàòîðà äëÿ ïàðû âåðøèí ( , )x y . Â òðåõ äðóãèõ
ñëó÷àÿõ îðèåíòàöèè ïàðû ðåáåð x z y— — âåðøèíà z ÿâëÿåòñÿ îáÿçàòåëüíûì
÷ëåíîì ëþáîãî ñåïàðàòîðà äëÿ ïàðû âåðøèí ( , )x y .
Íåêîëëàéäåðíàÿ âåðøèíà z íà ïóòè x z y— — ÿâëÿåòñÿ «ñòåðæíåì» (pivot)
ñåïàðàòîðà äëÿ ( , )x y .
Ôàêò 8 (ïðàâèëî ìíîæåñòâà èçîëèðîâàííûõ îáùèõ áëèçêèõ; set of isolated
common covariates). Ïóñòü â ÀÎÃ âåðíî � � �Ds ( )x y è R — ìíîæåñòâî âñåõ âåð-
øèí, çàâèñèìûõ îäíîâðåìåííî îò x è y, ò.å. R � � � � � �{ Ds Ds }r r x r y| ( ) & ( ) ,
ïðè÷åì | |R � 2, è äëÿ êàæäîé ïàðû r z, �R âåðíî Ds ( )r z� � . Òîãäà ëèáî ñóùåñ-
òâóåò ðåáðî x y— , ëèáî ìíîæåñòâî R — åäèíñòâåííûé ëîêàëüíî-ìèíèìàëüíûé ñåïà-
ðàòîð äëÿ ïàðû ( , )x y .
Ôàêò 8 ñëåäóåò èç ôàêòîâ 4, 7. Çàìåòèì, ÷òî (â óñëîâèÿõ ôàêòà 8) âñå âåðøè-
íû ìíîæåñòâà R ÿâëÿþòñÿ êîðíåâûìè, à âåðøèíû x è y íå èìåþò íè îäíîãî ðå-
áåíêà, åñëè íå áðàòü âî âíèìàíèå âîçìîæíîãî ðåáðà x y— . Âîçìîæíû òðè ñëó-
÷àÿ: 1) âñå r �R ÿâëÿþòñÿ îáùèìè ðîäèòåëÿìè äëÿ x è y; 2) ïîäìíîæåñòâî âåð-
øèí ìíîæåñòâà R — îáùèå ðîäèòåëè äëÿ x è y, à îñòàëüíûå ÷ëåíû R —
ðîäèòåëè òîëüêî âåðøèíû x; 3) âñå âåðøèíû r �R ÿâëÿþòñÿ ðîäèòåëÿìè òîëüêî
âåðøèíû x. (Ñèììåòðè÷íûå âàðèàíòû íå íàçûâàåì.)  ñëó÷àå 1) ðåáðî x y— âîç-
ìîæíî.  ñëó÷àÿõ 2) è 3) îáÿçàòåëüíî åñòü äóãà x y� .  ñëó÷àå 3) âåðíî
Ds ( )R � �x y .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 23
Ôàêò 9. Â ïðîèçâîëüíîì ÀÎÃ ñåïàðàòîðîì äëÿ ïàðû íåñìåæíûõ âåðøèí ( , )x y
ÿâëÿåòñÿ ìíîæåñòâî âñåõ ðîäèòåëåé âåðøèíû x èëè ìíîæåñòâî âñåõ ðîäèòåëåé âåðøè-
íû y, èëè êàæäîå èç ýòèõ ìíîæåñòâ. Òàêæå ñåïàðàòîðîì äëÿ ïàðû ( , )x y ÿâëÿåòñÿ
îáúåäèíåíèå âñåõ ðîäèòåëåé îáåèõ âåðøèí x è y.
Äîêàçàòåëüñòâî. Î÷åâèäíî, ÷òî íå ìîãóò ñóùåñòâîâàòü îäíîâðåìåííî
îðïóòü x y� ��� � è îðïóòü y x� ��� � . Ïóñòü (òåõíè÷åñêè) íåò íè îäíîãî îðïó-
òè y x� ��� � . Òîãäà ñåïàðàòîðîì äëÿ ( , )x y áóäåò ìíîæåñòâî ðîäèòåëåé âåðøè-
íû y. Ïðåäïîëîæèì ïðîòèâíîå. Òîãäà ìåæäó âåðøèíàìè x è y ñóùåñòâóåò íåêî-
òîðûé ïóòü �, îòêðûòûé ïðè êîíäèöèîíèðîâàíèè ðîäèòåëåé âåðøèíû y. Ñëåäîâà-
òåëüíî, êðàéíåé äóãîé ïóòè � äîëæíà áûòü y �. Çíà÷èò, åñëè ïóòü � —
áåñêîëëàéäåðíûé (ò.å. öåïü), òî îí èìååò âèä y x� ��� � . Íî ýòî ïðîòèâîðå÷èò òåõíè-
÷åñêîìó äîïóùåíèþ. Åñëè ïóòü � — êîëëàéäåðíûé, ðàññìîòðèì áëèæàéøèé ê âåðøè-
íå y êîëëàéäåð � �z . ßñíî, ÷òî åñòü îðïóòü âèäà y z� ��� � . Òàê êàê ýòîò êîëëàéäåð
äîëæåí áûòü îòêðûò ïðè êîíäèöèîíèðîâàíèè ðîäèòåëåé âåðøèíû y, äîëæåí ñóùåñòâî-
âàòü îðïóòü âèäà z y� ��� � . Ïîëó÷àåì îðöèêë. Èòàê, ïðåäïîëîæåíèå îò ïðîòèâíîãî
áûëî íåâåðíûì. Ñëåäîâàòåëüíî, åñëè íåò íè îäíîãî îðïóòè ìåæäó âåðøèíàìè x è y (íè
â êàêîì íàïðàâëåíèè), òî ñåïàðàòîðîì äëÿ ( , )x y ÿâëÿåòñÿ è ìíîæåñòâî âñåõ ðîäèòåëåé
âåðøèíû x, è ìíîæåñòâî âñåõ ðîäèòåëåé âåðøèíû y. Îñòàëüíîå äîêàçàòü ëåãêî.
Îòìåòèì, ÷òî áûâàþò ñëó÷àè, êîãäà ñåïàðàòîð äëÿ ïàðû âåðøèí ( , )x y ñó-
ùåñòâóåò, íî íèêàêîå ïîäìíîæåñòâî ìíîæåñòâà âåðøèí, ñìåæíûõ ñ x, â òîì ÷èñ-
ëå âñå ýòî ìíîæåñòâî, íå ÿâëÿåòñÿ ñåïàðàòîðîì äëÿ ( , )x y . Ïîíÿòíî, ÷òî â òàêîì
ñëó÷àå ñåïàðàòîð ìîæíî ñîñòàâèòü èç âåðøèí, ñìåæíûõ ñ y.
Èç ôàêòà 9 ñëåäóåò: åñëè â ÀÎÃ íå ñóùåñòâóåò ðåáðà x y— , òî ñåïàðàòîð äëÿ
ïàðû ( , )x y ñóùåñòâóåò.
Óòâåðæäåíèå 3. Åñëè â ÀÎÃ âåðøèíà w âõîäèò â ñîñòàâ íåêîòîðîãî ñåïàðà-
òîðà äëÿ ïàðû âåðøèí ( , )x y è ñóùåñòâóþò âåðøèíû q z, òàêèå, ÷òî âåðíî
Ds ( )w q x� � è Ds ( )w z y� � , òî ñóùåñòâóåò ñåïàðàòîð äëÿ ïàðû âåðøèí ( , )x y ,
êîòîðûé íå ñîäåðæèò âåðøèíó w.
Äåéñòâèòåëüíî, òàêèì ñåïàðàòîðîì (âîçìîæíî, íå ìèíèìàëüíûì) ÿâëÿåòñÿ
îáúåäèíåíèå âñåõ ðîäèòåëåé âåðøèí x è y. Óòâåðæäåíèå 3 ëåãêî îáîáùèòü
ñëåäóþùèì îáðàçîì.
Óòâåðæäåíèå 4.Åñëè â ÀÎÃ âåðøèíà w âõîäèò â ñîñòàâ íåêîòîðîãî ñåïàðà-
òîðà äëÿ ïàðû âåðøèí ( , )x y è ñóùåñòâóþò ìíîæåñòâà âåðøèí R S, òàêèå, ÷òî
âåðíî Ds ( )w x� �R è Ds ( )w y� �S , òî ñóùåñòâóåò ñåïàðàòîð äëÿ ïàðû âåðøèí
( , )x y , êîòîðûé íå ñîäåðæèò âåðøèíó w.
Óòâåðæäåíèÿ 3, 4 è ôàêò 9 îïðàâäûâàþò òàêòèêó àëãîðèòìà PC, êîòîðûé ïðè
ïîèñêå ñåïàðàòîðà äëÿ ( , )x y îòáðàñûâàåò âñå âåðøèíû, íå ñìåæíûå ñ x è y. Òàêàÿ
òàêòèêà öåëåñîîáðàçíà ñ òî÷êè çðåíèÿ áûñòðîãî ñî-
êðàùåíèÿ ìíîæåñòâà êàíäèäàòîâ â ÷ëåíû ñåïàðàòî-
ðà, íî â òî æå âðåìÿ îíà ÷àñòî âåäåò ê ïîòåðå ìèíè-
ìàëüíûõ ñåïàðàòîðîâ. Ýòî ìîæíî ïðîèëëþñòðèðî-
âàòü íà ïðèìåðå ìîäåëè, èçîáðàæåííîé íà ðèñ. 2.
Àëãîðèòì PC íàéäåò ôàêòû Ds ( )w q x� � è
Ds ( )w z y� � è ïîýòîìó èñêëþ÷èò âåðøèíó w èç
ðàññìîòðåíèÿ ïðè ïîèñêå ñåïàðàòîðà äëÿ ( , )x y . Çíà-
÷èò, â äàëüíåéøåì àëãîðèòì óæå íå ñìîæåò íàéòè ìè-
íèìàëüíûé ñåïàðàòîð { }q w z, , . (Çàìåòèì, ýòîò ñåïàðà-
òîð ñîñòîèò èç âåðøèí, íå ñìåæíûõ ñ x è y.) Àëãîðèòì PC òàêæå íàéäåò ôàêòû
Ds { }( , )x q g h� � è Ds { }( , )y z r t� � . Çàòåì îí ñ ïîìîùüþ ñåïàðàòîðà, ñîñòîÿùå-
ãî èç äâóõ íåèìåíîâàííûõ âåðøèí, ïîêàçàííûõ íà ðèñóíêå êðóæêàìè, èñêëþ÷èò
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ðèñ. 2
âåðøèíó q èç ÷èñëà ñìåæíûõ ñ x è, ñèììåòðè÷íî, èñêëþ÷èò âåðøèíó z èç ÷èñëà
ñìåæíûõ ñ y. Â ðåçóëüòàòå àëãîðèòì óæå íå ñìîæåò íàéòè ñåïàðàòîðû { }g h z, , è
{ }t r q, , . Ñëåäîâàòåëüíî, íè îäèí ìèíèìàëüíûé ñåïàðàòîð íå áóäåò íàéäåí (áóäåò
íàéäåí ñåïàðàòîð èç ÷åòûðåõ ïåðåìåííûõ).
Ëåãêî ïîñòðîèòü ïðèìåðû, ãäå ñåïàðàòîðû, íàéäåííûå àëãîðèòìîì PC, áóäóò íà-
ìíîãî ñëîæíåå ìèíèìàëüíûõ. Äàëåå èçëàãàþòñÿ ãëàâíûå ðåçóëüòàòû.
Óòâåðæäåíèå 5 (áàçîâàÿ òåîðåìà î ÷ëåíàõ ëîêàëüíî-ìèíèìàëüíîãî ñåïàðà-
òîðà). Åñëè â ÀÎÃ âåðøèíà z âõîäèò â ñîñòàâ íåêîòîðîãî ëîêàëüíî-ìèíèìàëüíî-
ãî ñåïàðàòîðà äëÿ ïàðû âåðøèí ( , )x y , òî:
a) ñóùåñòâóåò íåêîòîðûé îðèåíòèðîâàííûé ïóòü îò âåðøèíû z äî âåðøèíû
x, íå ïðîõîäÿùèé ÷åðåç y, èëè ñóùåñòâóåò íåêîòîðûé îðèåíòèðîâàííûé ïóòü îò
âåðøèíû z äî âåðøèíû y, íå ïðîõîäÿùèé ÷åðåç x;
á) åñëè íå ñóùåñòâóåò íè îäíîé öåïè ìåæäó âåðøèíàìè x è z, êîòîðàÿ íå ïðî-
õîäèò ÷åðåç y, òî ñóùåñòâóþò (ïî ìåíüøåé ìåðå) äâå íåêîòîðûå öåïè �1 è � 2 ìåæ-
äó âåðøèíàìè z è y, êîòîðûå çàêàí÷èâàþòñÿ äóãàìè � y è íå ïðîõîäÿò ÷åðåç x.
Çàìåòèì, ÷òî öåïè �1 è � 2 ìîãóò âçàèìíî íàëàãàòüñÿ è ïåðåñåêàòüñÿ, íî èõ
îòðåçêè, ïðèëåãàþùèå ê âåðøèíå z, íå ñîâïàäàþò. Êðîìå òîãî, îðèåíòèðîâàííûé
ïóòü, íàçâàííûé â ï. à) òåîðåìû, ìîæåò ñîâïàäàòü ñ îäíîé èç öåïåé �1 èëè � 2 ,
óïîìÿíóòûõ â ï. á) òåîðåìû.
Äîêàçàòåëüñòâî áàçîâîé òåîðåìû äàíî â [12].
Ôîðìóëèðîâêà áîëåå ðàííåãî âàðèàíòà òåîðåìû èç
[11] íåòî÷íà, ÷òî óæå îòìå÷àëîñü âûøå (ïîñëå ôàê-
òà 3). Áàçîâàÿ òåîðåìà èëëþñòðèðóåòñÿ íà ðèñ. 3, ãäå
ëîêàëüíî-ìèíèìàëüíûìè ñåïàðàòîðàìè äëÿ ( , )x y
ÿâëÿþòñÿ { }q z, è { }r u w, , . Ïðè ýòîì íå ñóùåñòâóåò
íè îäíîé öåïè ìåæäó âåðøèíîé x è âåðøèíàìè z, u,
w (êîòîðûå ÿâëÿþòñÿ ÷ëåíàìè ñîîòâåòñòâóþùèõ
S x ylom ( , )). Â òî æå âðåìÿ èç êàæäîé âåðøèíû
z u w, , åñòü ïî äâà îðïóòè â y, êîòîðûå íå ïðîõîäÿò ÷åðåç x. Ïðè÷åì îðïóòè
z q r y� � � è z r y� � âçàèìíî íàëàãàþòñÿ. Îáðàùàåì âíèìàíèå, ÷òî, íå-
ñìîòðÿ íà òî, ÷òî âñå öåïè ìåæäó âåðøèíàìè z è y ïðîõîäÿò ÷åðåç âåðøèíó r,
ìèíèìàëüíûé ñåïàðàòîð äëÿ ( , )x y âêëþ÷àåò âåðøèíó z, à íå âåðøèíó r. Òåïåðü
îáðàòèìñÿ ê ìîäåëè íà ðèñ. 1 è óáåäèìñÿ, ÷òî r S x y� min ( , ). Ïðè ýòîì âåðøèíà r
ñîåäèíåíà ñ âåðøèíîé y îäíèì îðïóòåì r z y� � è åùå ÷åòûðüìÿ öåïÿìè.
Èç áàçîâîé òåîðåìû íåìåäëåííî âûòåêàåò ñëåäóþùåå.
Ôàêò 10. Åñëè âåðíî Ds Ds( ) & ( )w x w y� � � � , òî w S x y� lom ( , ).
Ôàêò 11 (ïðàâèëî «÷óæîãî ãåíà»). Åñëè â îðãðàôå äëÿ çàäàííîé âåðøèíû z
ñóùåñòâóåò òàêàÿ âåðøèíà w, ÷òî � � �Ds ( )w z , Ds ( )w x� � , Ds ( )w y� � , òî
âåðøèíà z íå âõîäèò â ñîñòàâ íèêàêîãî ëîêàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà äëÿ
ïàðû âåðøèí ( , )x y .
(Çàìåòèì, ÷òî ýòî ïðàâèëî ðàáîòàåò òàêæå è â ñëó÷àå ñóùåñòâîâàíèÿ x y— .)
Ôàêò 11 ñëåäóåò èç ï. à) áàçîâîé òåîðåìû è ôàêòà 4. Ýêâèâàëåíòíàÿ ôîðìóëèðîâ-
êà ýòîãî ïðàâèëà áûëà âûðàæåíà â àïïàðàòå ãåíîòèïîâ ïåðåìåííûõ [11].
Ôàêò 12 (ïðàâèëî «èçîëÿòîðà»). Ïóñòü â ÀÎÃ èìååì � � �Ds ( )x y è äëÿ
âåðøèí z è r âåðíî � � �Ds ( )z x , Ds ( )z y� � , Ds ( )r x� � , � � �Ds ( )r y . Òîãäà
åñëè ñóùåñòâóåò òàêàÿ âåðøèíà w (w x� , w y� ), ÷òî � � �Ds ( )w z è
� � �Ds ( )w r , òî ñåïàðàòîð äëÿ ïàðû âåðøèí ( , )x y ñóùåñòâóåò, à âåðøèíà w íå
âõîäèò â ñîñòàâ íèêàêîãî ëîêàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà äëÿ ïàðû ( , )x y .
Äîêàçàòåëüñòâî. Âûâîä î ñóùåñòâîâàíèè ñåïàðàòîðà ïîâòîðÿåò óòâåðæäå-
íèå 1 (ïðàâèëî íåïîãëîùåíèÿ). Äëÿ äîêàçàòåëüñòâà îñòàëüíîãî ïðåäïîëîæèì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 25
Ðèñ. 3
ïðîòèâíîå, ò.å. ÷òî w S x y� lom ( , ). Òîãäà, ñîãëàñíî ïóíêòó à) áàçîâîé òåîðåìû,
äîëæåí ñóùåñòâîâàòü îðïóòü w x� �� � � èëè îðïóòü w y� �� � � .  ïåðâîì ñëó-
÷àå ââèäó � � �Ds ( )w r è ôàêòà 4 ïîëó÷èì � � �Ds ( )r x , ÷òî ïðîòèâîðå÷èò
óñëîâèþ. Âî âòîðîì ñëó÷àå àíàëîãè÷íî ïîëó÷àåì � � �Ds ( )z y , ò.å. ïðîòèâîðå-
÷èå óñëîâèþ. (Ïî àíàëîãèè ñ ôàêòîì 11, ìîæíî ñêàçàòü, ÷òî âåðøèíà w
èçîëèðóåò äâà «ïîëó÷óæèõ ãåíà».)
Ïðîäîëæåíèåì è óòî÷íåíèåì áàçîâîé òåîðåìû ñëóæèò ñëåäóþùåå
óòâåðæäåíèå.
Óòâåðæäåíèå 6. Åñëè âåðíî z S x y� lom ( , ) S è Ds ( )x z� � , òî:
a) ñóùåñòâóåò íåêîòîðàÿ öåïü ìåæäó âåðøèíàìè x è y, êîòîðàÿ íå ïðîõîäèò
÷åðåç z;
á) âñå öåïè ìåæäó âåðøèíàìè x è y, à òàêæå âñå öåïè ìåæäó âåðøèíàìè z è
y çàêàí÷èâàþòñÿ äóãàìè � y;
â) ñðåäè âñåõ ïóòåé ìåæäó âåðøèíàìè x è y, êîòîðûå ïðîõîäÿò ÷åðåç z, åñòü
íåêîòîðûé ïóòü �, íà êîòîðîì âñå êîëëàéäåðû îòêðûòû ïðè êîíäèöèîíèðîâàíèè
S \ { }z .
Äîêàçàòåëüñòâî. Ïóíêò à) ñëåäóåò èç óòâåðæäåíèÿ 2. Ïåðåõîäèì ê ï. á).
Åñëè áû ñóùåñòâîâàëà öåïü ìåæäó âåðøèíàìè x è y, êîòîðàÿ íå çàêàí÷èâàåòñÿ
äóãîé � y, òî ýòî áûë áû îðïóòü x y� �� � � ; íî òîãäà, ââèäó ñóùåñòâîâàíèÿ
îðïóòè z y� �� � � (áàçîâàÿ òåîðåìà), ïîëó÷èëè áû öåïü z x� �� � � , ÷òî ïðîòè-
âîðå÷èò óñëîâèþ. Àíàëîãè÷íî, ê ïðîòèâîðå÷èþ ïðèâîäèò äîïóùåíèå, ÷òî åñòü
öåïü ìåæäó z è y, êîòîðàÿ íå çàêàí÷èâàåòñÿ äóãîé � y. Ïóíêò â) ñëåäóåò èç
óñëîâèÿ z S x y� lom ( , ).
Çàìåòèì, ÷òî íà êàæäîì ïóòè, óäîâëåòâîðÿþùåì ï. â), êîëè÷åñòâî êîëëàéäå-
ðîâ îãðàíè÷åíî ñâåðõó òîëüêî êàðäèíàëüíîñòüþ S.
Èç óòâåðæäåíèÿ 6 ñëåäóåò, ÷òî êîãäà ìåæäó âåðøèíîé z, z S x y� lom ( , ), è
âåðøèíîé x íåò íè îäíîé öåïè, ìåæäó íèìè îáÿçàòåëüíî åñòü ïóòü � ñ îäíèì
êîëëàéäåðîì. Ñóùåñòâîâàíèå òàêîãî ïóòè âûòåêàåò èç ôàêòà ñóùåñòâîâàíèÿ
öåïè x y� � � � � , êîòîðàÿ íå ïðîõîäèò ÷åðåç z, è ôàêòà ñóùåñòâîâàíèÿ îðïóòè
z y� �� � � . Ïðè÷åì åäèíñòâåííîé êîëëàéäåðíîé âåðøèíîé íà ïóòè � ÿâëÿåòñÿ
ëèáî âåðøèíà y, ëèáî êàêîé-òî åå ïðåäîê.
Ôàêò 13. Åñëè âåðíî z S x y� lom ( , ) è Ds ( )x z� � , òî � � �Ds ( )x y z .
Ôàêò 13 ñëåäóåò èç ïï. à) è á) óòâåðæäåíèÿ 6.
Óòâåðæäåíèå 7 (ïðàâèëî äâîéíîãî 1-îòñå÷åíèÿ; double 1-cutting). Åñëè äëÿ
çàäàííîé ïàðû âåðøèí ( , )x y ñóùåñòâóåò òàêàÿ âåðøèíà z, ÷òî âûïîëíÿåòñÿ
Ds ( )w z x� � è Ds ( )w z y� � , òî âåðøèíà w íå âõîäèò â ñîñòàâ íèêàêîãî ëî-
êàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà äëÿ ïàðû âåðøèí ( , )x y .
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì îáðàòíîå, ò.å. ïóñòü â óñëîâèÿõ óòâåðæäå-
íèÿ áóäåò w S x y� lom ( , ) S. Åñëè ïðåäïîëîæèòü, ÷òî âåðøèíà w ëåæèò íà íåêî-
òîðîé öåïè ìåæäó âåðøèíàìè x è y, òî íåâîçìîæíî îäíîâðåìåííîå âûïîëíåíèå
Ds ( )w z x� � è Ds ( )w z y� � íè äëÿ êàêîé z. Ñëåäîâàòåëüíî, w íå ëåæèò íè íà
êàêîé öåïè ìåæäó âåðøèíàìè x è y. Ïóñòü äëÿ îïðåäåëåííîñòè èìååì ñëó÷àé
Ds ( )w x� � . Òîãäà, ñîãëàñíî áàçîâîé òåîðåìå, åñòü îðïóòü w y� �� � � , êîòîðûé
íå ïðîõîäèò ÷åðåç x. Ðàññìîòðèì ïóòü �, ìåæäó x è y, êîòîðûé çàêðûâàåòñÿ ñ ïî-
ìîùüþ âåðøèíû w. ßñíî, ÷òî âñå êîëëàéäåðû íà ó÷àñòêå ïóòè � ìåæäó âåðøèíà-
ìè x è w îòêðûòû ïðè êîíäèöèîíèðîâàíèè ìíîæåñòâà âåðøèí S \ { }w . Ðàññìîò-
ðèì áëèæàéøèé ê âåðøèíå w êîëëàéäåð � �q1 íà ýòîì ó÷àñòêå ïóòè �. Òàê êàê
îí îòêðûò, åñòü îðïóòü èç q1 â îäíó èç âåðøèí t1, âõîäÿùèõ â ñîñòàâ S \ { }w . Â
ñâîþ î÷åðåäü (ñîãëàñíî áàçîâîé òåîðåìå), èìååòñÿ îðïóòü èç t1 â âåðøèíó y. Çíà-
÷èò, äëÿ âûïîëíåíèÿ Ds ( )w z y� � íåîáõîäèìî, ÷òîáû ýòîò îðïóòü èç q1 â âåð-
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
øèíó y áëîêèðîâàëñÿ ñ ïîìîùüþ z. (Èíà÷å îáðàçóåòñÿ öåïü ìåæäó âåðøèíàìè w
è y, íå áëîêèðóåìàÿ ñ ïîìîùüþ z.) Íî òîãäà êîíäèöèîíèðîâàíèå âåðøèíû z îò-
êðûâàåò êîëëàéäåð � �q1 íà ïóòè �. Ðàññìîòðèì ñëåäóþùèé êîëëàéäåð
� �q2 íà ýòîì ó÷àñòêå ïóòè �. Ïîñêîëüêó îí òîæå îòêðûò ïðè êîíäèöèîíèðî-
âàíèè ìíîæåñòâà âåðøèí S \ { }w , àíàëîãè÷íûå ðàññóæäåíèÿ ïðèâåäóò ê âûâîäó,
÷òî åñòü îðïóòü èç âåðøèíû q2 â âåðøèíó z. Ñëåäîâàòåëüíî, êîëëàéäåð � �q2
íà ïóòè � òàêæå îòêðûò ïðè êîíäèöèîíèðîâàíèè âåðøèíû z. Òàêèì îáðàçîì, ïðè
êîíäèöèîíèðîâàíèè âåðøèíû z îòêðûòû êîëëàéäåðû � �q1 è � �q2 , ñëåäî-
âàòåëüíî, îòêðûò îòðåçîê ïóòè � ìåæäó âåðøèíàìè w è òðåòüèì êîëëàéäåðîì
� �q3 . Ïîâòîðÿÿ ðàññóæäåíèÿ ïî ýòîé ñõåìå íå áîëåå ÷åì (| |S �1) ðàç, ïðèõî-
äèì ê âûâîäó, ÷òî èç êàæäîãî êîëëàéäåðà qi íà ïóòè � èìååòñÿ îðïóòü â âåðøèíó
z. Ñëåäîâàòåëüíî, íåâåðíî Ds ( )w z x� � . ( äðóãîì ñëó÷àå ïîëó÷èì, ÷òî
íåâåðíî Ds ( )w z y� � ).
 [12] ïîêàçàíî, ÷òî óòâåðæäåíèå 7 íåëüçÿ ðàñøèðèòü äî ïðàâèëà
[ : ( )] ( , )
� � � �z w z x w S x yDs lom . Ïðèìåíåíèå òàêîãî ïðàâèëà ìîæåò ïðèâåñ-
òè íå òîëüêî ê ïîòåðå ìèíèìàëüíîãî ñåïàðàòîðà, íî ê ïîòåðå âñåõ ñåïàðàòîðîâ
äëÿ ïàðû âåðøèí ( , )x y . Óòâåðæäåíèå 7 òàêæå íåëüçÿ ðàñøèðèòü äî ïðàâèëà âèäà
[ , : ( ) & ( )] ( , )
� � � � � �q z w q x w z y w S x yDs Ds lom . (6)
Ïðèìåíåíèå ïðàâèëà (6) ìîæåò ïðèâåñòè òîëüêî ê ïîòåðå ìèíèìàëüíîãî ñåïà-
ðàòîðà, íî íå ê ïîòåðå âñåõ ñåïàðàòîðîâ äëÿ ïàðû âåðøèí ( , )x y . Ýòî ïîÿñíÿ-
ëîñü â êîììåíòàðèè ê ðèñ. 2. (Åñëè ìîäåëü ñîäåðæèò ñêðûòûå ïåðåìåííûå,
ïðàâèëî (6) ìîæåò ïðèâåñòè ê ïîòåðå âñåõ ñåïàðàòîðîâ äëÿ ïàðû ( , )x y .)
Óòâåðæäåíèå 7 è ïðàâèëî (6) âñòðîåíû â àëãîðèòì PC.
Äëÿ èíòåíñèâíîãî ñîêðàùåíèÿ ÷èñëà êàíäèäàòîâ â ñåïàðàòîðû ìîæíî íàéòè
è äðóãèå âîçìîæíîñòè. Èíòóèòèâíî êàæåòñÿ óáåäèòåëüíûì òàêîå ñóæäåíèå: åñëè
îäíà èç âåðøèí ïàðû ( , )x y ñåïàðèðóåò äðóãóþ âåðøèíó ïàðû ( , )x y îò âåðøèíû
z, òî âåðøèíà z íå ÿâëÿåòñÿ ÷ëåíîì íèêàêîãî S x ylom ( , ). Èíà÷å ãîâîðÿ, êîãäà, íà-
ïðèìåð, âåðøèíà x ñåïàðèðóåò âåðøèíó z îò âåðøèíû y, òî ìîæíî ñêàçàòü, ÷òî
âåðøèíà z «îòñòðàíÿåòñÿ» îò ïàðû ( , )x y . Ôîðìàëüíî ïîëó÷àåì ñëåäóþùåå
óòâåðæäåíèå.
Óòâåðæäåíèå 8.Åñëè Ds ( )z x y� � , òî z S x y� lom ( , ). (Ïðè ýòîì ìîæíî íå
óòî÷íÿòü, ñóùåñòâóåò ñåïàðàòîð äëÿ ïàðû âåðøèí ( , )x y èëè íåò.)
Äîêàçàòåëüñòâî. Äîïóñòèì ïðîòèâíîå. Ïóñòü âåðøèíà z âõîäèò â ñîñòàâ íå-
êîòîðîãî ëîêàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà äëÿ ïàðû âåðøèí ( , )x y . Åñëè âåð-
øèíà z ëåæèò íà íåêîòîðîé öåïè ìåæäó âåðøèíàìè x è y, òî ïîíÿòíî, ÷òî íè
Ds ( )z x y� � , íè Ds ( )z y x� � íå âûïîëíÿåòñÿ, ò.å. èìååì ïðîòèâîðå÷èå óñëî-
âèþ. Îñòàåòñÿ ïðåäïîëîæèòü, ÷òî âåðøèíà z íå ëåæèò íè íà êàêîé öåïè ìåæäó
âåðøèíàìè x è y. Òîãäà z ëåæèò íà íåêîòîðîì êîëëàéäåðíîì ïóòè ìåæäó x è y,
òàê ÷òî èìååì Ds ( )z x� � èëè Ds ( )z y� � . Êðîìå òîãî, ñîãëàñíî áàçîâîé òåîðå-
ìå çàêëþ÷àåì: à) åñòü îðïóòü èç z â âåðøèíó x, íå ïðîõîäÿùèé ÷åðåç y; èëè á) åñòü
îðïóòü èç z â âåðøèíó y, íå ïðîõîäÿùèé ÷åðåç x. Ââèäó óñëîâèÿ Ds ( )z x y� �
ñëó÷àé á) îòïàäàåò. Çíà÷èò, åñòü îðïóòü èç z â âåðøèíó x, íå ïðîõîäÿùèé ÷åðåç y;
è âåðíî Ds ( )z y� � . Òîãäà ñîãëàñíî ôàêòó 13 èç z S x y� lom ( , ) è Ds ( )z y� �
ñëåäóåò � � �Ds ( )z x y , ò.å. ïîëó÷àåì ïðîòèâîðå÷èå óñëîâèþ.
 [12] óòâåðæäåíèå 8 äîêàçàíî èíà÷å. Ìîæíî óñèëèòü ýòî óòâåðæäåíèå (ñäå-
ëàòü åãî áîëåå íàäåæíûì ýìïèðè÷åñêè) ñëåäóþøèì îáðàçîì.
Ôàêò 14 (îòñòðàíåíèå âåðøèíû; placing aside). Ñïðàâåäëèâî
Ds Ds lom( ) & ( ) ( , )z x y z y z S x y� � � � � � � . (7)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 27
 [12] ïðåäëîæåíî ïðàâèëî «áûñòðîé» èäåíòèôèêàöèè ðåáðà, èñïîëüçóþùåå
åäèíñòâåííîñòü íåîòñòðàíåííîãî êàíäèäàòà.
Ñîãëàñíî óòâåðæäåíèþ 2 ñïðàâåäëèâ ñëåäóþùèé ôàêò.
Ôàêò 15 (íåîòñòðàíÿåìûé ïîòåíöèàëüíûé ñòåðæåíü ñåïàðàòîðà). Åñëè ñó-
ùåñòâóåò ñåïàðàòîð äëÿ ïàðû âåðøèí ( , )x y , òî ñóùåñòâóåò òàêàÿ âåðøèíà z
( z x� , z y� ) , ÷òî � � �Ds ( )z x , � � �Ds ( )z y , � � �Ds ( )z x y è
� � �Ds ( )z y x .
Îïðåäåëåíèå 7. Âåðøèíà z íàçûâàåòñÿ ïîòåíöèàëüíûì ñòåðæíåì ñå-
ïàðàòîðà (potent ia l pivot of separator) äëÿ ïàðû âåðøèí ( , )x y , åñëè
� � � � � � � � � � � �Ds Ds Ds Ds( ) & ( ) & ( ) & ( ) &x y z x z y z x y
& ( )� � �Ds z y x .
Ïóñòü U — ìíîæåñòâî âñåõ âåðøèí ãðàôà. Òîãäà ñîãëàñíî ôàêòó 15 ïîëó÷à-
åì ñëåäóþùåå ïðàâèëî «áûñòðîé» èäåíòèôèêàöèè ðåáðà (èäåíòèôèêàöèÿ ïåðå-
ìû÷êè; identification of bottleneck):
� � � � � � � � � �Ds { } Ds Ds( ) & ( \ , :[ ( ) ( )x y z x y z x z yU
� � � � � � �Ds Ds( ) ( )]) —z x y z y x x y, (8)
ãäå � îçíà÷àåò äèçúþíêöèþ.
Êàê ïîêàçàíî â [12], åäèíñòâåííûé ïîòåíöèàëüíûé ñòåðæåíü ñåïàðàòîðà äëÿ
( , )x y ÿâëÿåòñÿ îáÿçàòåëüíûì ÷ëåíîì ëþáîãî ñåïàðàòîðà äëÿ ( , )x y (ðàçóìååòñÿ,
êîãäà íåò ðåáðà x y— è êîãäà ïóñòîå ìíîæåñòâî íå ÿâëÿåòñÿ ñåïàðàòîðîì äëÿ
( , )x y ).
Ñîâîêóïíîñòü ïðåäëîæåííûõ óòâåðæäåíèé è ôàêòîâ ïîçâîëÿåò ôîðìèðîâàòü
ìíîãî äðóãèõ ïîëåçíûõ ïðàâèë âûâîäà.
ÎÁÑÓÆÄÅÍÈÅ È ÎÖÅÍÊÀ
Îáîñíîâàííûå âûøå ïîëîæåíèÿ è ïðàâèëà èñïîëüçóþò â êà÷åñòâå ïðèçíàêîâ
ôàêòû çàâèñèìîñòè, íåçàâèñèìîñòè è íåêîòîðûå ôðàãìåíòû ñòðóêòóðû ìîäåëè,
à â êà÷åñòâå âûâîäà õàðàêòåðèçóþò äðóãèå ôðàãìåíòû ñòðóêòóðû ìîäåëè.
Ñìûñë (íàçíà÷åíèå) áîëüøèíñòâà ïðåäëîæåííûõ ïîëîæåíèé è ôàêòîâ
ñëåäóþùèé:
• ðàñïîçíàâàíèå ðåáåð;
• ðàñïîçíàâàíèå ñóùåñòâîâàíèÿ ñåïàðàòîðà (ò.å. îòñóòñòâèÿ ðåáðà);
• èäåíòèôèêàöèÿ íåâõîæäåíèÿ âåðøèíû â ñîñòàâ ëîêàëüíî-ìèíèìàëüíîãî
ñåïàðàòîðà.
Äëÿ ýòîãî óñòàíîâëåíû íåîáõîäèìûå òðåáîâàíèÿ ê ÷ëåíàì (ëîêàëüíî-ìèíè-
ìàëüíîãî) ñåïàðàòîðà. Äîñòàòî÷íûå òðåáîâàíèÿ ê ÷ëåíàì ëîêàëüíî-ìèíèìàëüíî-
ãî ñåïàðàòîðà (ðàçóìååòñÿ, êîãäà ñîîòâåòñòâóþùèé ñåïàðàòîð åùå íå íàéäåí è íå
âåðèôèöèðîâàí) ïðåäïîëàãàþò çíàíèå, ÷òî ñîîòâåòñòâóþùåå ðåáðî îòñóòñòâóåò.
Èíîãäà òàêîå çíàíèå ìîæåò áûòü âûâåäåíî èíäóêòèâíî. Òîãäà ìîæíî èíäóêòèâ-
íî èäåíòèôèöèðîâàòü âåðøèíó êàê ÷ëåíà ëîêàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà.
Íàïðèìåð, äîñòàòî÷íûå óñëîâèÿ äëÿ z S x y� lom ( , ) ìîæíî ñôîðìèðîâàòü êàê
òàêîå ñî÷åòàíèå: 1) ïðàâèëî íåïîãëîùåíèÿ; 2) ïðàâèëî åäèíñòâåííîãî îáùåãî
áëèçêîãî èëè ïðàâèëî ìíîæåñòâà èçîëèðîâàííûõ îáùèõ áëèçêèõ.
Ïðåäëîæåííûå ñðåäñòâà (â ÷àñòíîñòè, íåîáõîäèìûå òðåáîâàíèÿ ê ÷ëåíàì ëî-
êàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà) ñëåäóåò âñòðîèòü â àëãîðèòì âûâîäà ñòðóêòó-
ðû ñ ïîìîùüþ íåñêîëüêèõ ïðèíöèïîâ. Ñîõðàíÿåì áàçîâûé ïðèíöèï âûâîäà,
ïðèíÿòûé â àëãîðèòìå PC: åñëè èñïûòàíû è îòâåðãíóòû âñå ïîäìíîæåñòâà èç
ìíîæåñòâà ïðàâäîïîäîáíûõ ÷ëåíîâ ñåïàðàòîðà äëÿ ïàðû ( , )x y , òî ñóùåñòâóåò
ðåáðî x y— . Îäíàêî ýôôåêòèâíîñòü ðàáîòû ýòîãî ïðèíöèïà ïîâûøàåòñÿ áëàãî-
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
äàðÿ ââåäåíèþ äîïîëíèòåëüíûõ òðåáîâàíèé ê êàíäèäàòàì â ÷ëåíû ñåïàðàòîðà è ê
ñîñòàâó ñåïàðàòîðà.  ÷àñòíîñòè, â ñîñòàâ êàæäîãî ñåïàðàòîðà äîëæåí âõîäèòü
õîòÿ áû îäèí ïîòåíöèàëüíûé ñòåðæåíü ñåïàðàòîðà. Ýòè òðåáîâàíèÿ è ïðàâèëà
÷àñòî ïîçâîëÿþò îòñåÿòü çíà÷èòåëüíî áîëüøå êàíäèäàòîâ â ñåïàðàòîð, à èíîãäà
— äàæå âñåõ êàíäèäàòîâ. Òîãäà ïîèñê ñåïàðàòîðà ðåçêî óïðîùàåòñÿ, à èíîãäà
ïðåêðàùàåòñÿ íà ðàííåì ýòàïå.  ïðåäåëå ïîëó÷àåì íîâûå ïðèíöèïû âûâîäà.
Ðåçîëþöèÿ ñìåæíîñòè. Åñëè íå îñòàëîñü íè îäíîãî íåîòñåÿííîãî êàíäèäàòà
â ñåïàðàòîðû äëÿ ïàðû àññîöèèðîâàííûõ âåðøèí ( , )x y , òî ñóùåñòâóåò ðåáðî
x y— .
Ýòîò ïðèíöèï ïîêðûâàåòñÿ ñëåäóþùèì.
Ýêñïðåññ-ðåçîëþöèÿ ñìåæíîñòè. Åñëè äëÿ ïàðû âåðøèí ( , )x y íå îñòàëîñü
íè îäíîãî çàáðàêîâàííîãî ïîòåíöèàëüíîãî ñòåðæíÿ ñåïàðàòîðà, òî ñóùåñòâóåò
ðåáðî x y— .
Äîïîëíèòåëüíî ïîêàçàíî, êàê ìîæåò ðàáîòàòü êîíöåïòóàëüíî íîâûé ïðè-
íöèï âûâîäà, êîòîðûé íå òðåáóåò íè ïîèñêà ñîîòâåòñòâóþùåãî ñåïàðàòîðà, íè
àíàëèçà è îòñåèâàíèÿ êàíäèäàòîâ â ñåïàðàòîð.
Ðåçîëþöèÿ íåñìåæíîñòè. Åñëè íàáîð ôàêòîâ ñâèäåòåëüñòâóåò î íåâîçìîæ-
íîñòè íè äóãè (îðïóòè) x y� , íè äóãè (îðïóòè) y x� , òî ðåáðî x y—
îòñóòñòâóåò.
Ñîâîêóïíîñòü ïðåäëîæåííûõ ñðåäñòâ îòêðûâàåò ïåðñïåêòèâû çíà÷èòåëüíî ïî-
âûñèòü âû÷èñëèòåëüíóþ ýôôåêòèâíîñòü èäåíòèôèêàöèè ñòðóêòóðû ìîäåëè.
Íàïîìíèì, ÷òî âñå ïîëó÷åííûå ðåçóëüòàòû ïðåäïîëàãàþò îòñóòñòâèå ñòðîãî
îðèåíòèðîâàííûõ öèêëîâ. Ñêðûòûå ïåðåìåííûå (îòîáðàæàåìûå äâó-îðèåíòèðî-
âàííûìè ðåáðàìè) ñ îïðåäåëåííûìè îãðàíè÷åíèÿìè äîïóñòèìû äëÿ íåêîòîðûõ
ïîëîæåíèé, îäíàêî íåäîïóñòèìû äëÿ óòâåðæäåíèé 1, 3, 4 è ôàêòîâ 6, 8–10, 12.
Ïîòåíöèàëüíûå âîçìîæíîñòè íåêîòîðûõ ïðåäëîæåííûõ èíñòðóìåíòîâ ìîæ-
íî ïðîäåìîíñòðèðîâàòü íà ïðèìåðå ìîäåëè, ïîêàçàííîé íà ðèñ. 4. Ýòîò ãðàô ñî-
ñòîèò èç 17 âåðøèí è 21 ðåáðà. Êàæäàÿ èç âåðøèí
x è y èìååò 13 áåçóñëîâíî çàâèñèìûõ âåðøèí (íå
ñ÷èòàÿ ñàìèõ x è y), ïðè÷åì äâå èç íèõ — ñîâìåñ-
òíûå ñìåæíûå äëÿ x è y. Åñëè ïðèìåíèòü ê ýòîìó
ïðèìåðó òàêòèêó àëãîðèòìà PC, òî äëÿ èäåíòèôèêà-
öèè ðåáðà x y— áóäåò âûïîëíåí ñëîæíûé ïåðåáîð
ñ èñïîëüçîâàíèåì òåñòîâ íåçàâèñèìîñòè âûñîêîãî
ïîðÿäêà. Ñ ïîìîùüþ ïðåäëîæåííûõ ñðåäñòâ ðåáðî
x y— èäåíòèôèöèðóåòñÿ íà îñíîâå ôàêòîâ (òåñòîâ)
óñëîâíîé íåçàâèñèìîñòè òîëüêî íóëåâîãî è ïåðâîãî
ïîðÿäêà.  ýòîì ïðèìåðå äîñòàòî÷íî ïðèìåíèòü
ïðàâèëî «÷óæîãî ãåíà», ïðàâèëî äâîéíîãî 1-îòñå÷åíèÿ è ïðàâèëî «îòñòðàíåíèÿ».
Ïðåäëîæåííûå ïîëîæåíèÿ è ïðàâèëà â òîì âèäå, êàê îíè ñôîðìóëèðîâàíû
âûøå, íåïîñðåäñòâåííî ïðèãîäíû äëÿ âûâîäà èç ñîâîêóïíîñòè (áàçû) çíàíèé î
ñèñòåìå çàâèñèìîñòåé. Äðóãèìè ñëîâàìè, ýòè ñðåäñòâà ñëóæàò äëÿ êîìïèëÿöèè
(ñèíòåçà) ìîäåëè èç îòäåëüíûõ çíàíèé. (Çàìåòèì, ÷òî çíàíèÿ â ôîðìå êàóçàëüíî-
ãî ïîðÿäêà ïåðåìåííûõ ñäåëàþò íåêîòîðûå ïðåäëîæåííûå èíñòðóìåíòû èçëèø-
íèìè.) Êðîìå òîãî, äàííûå ïðàâèëà ïðèìåíèìû äëÿ àíàëèçà ìîäåëè, â ÷àñòíîñòè
äëÿ ïëàíèðîâàíèÿ ñõåìû ðàññóæäåíèé íà çàäàííîé ìîäåëè, ò.å. äëÿ âûâîäà îò
ñâèäåòåëüñòâ ê öåëåâûì ïåðåìåííûì (â ýêñïåðòíûõ ñèñòåìàõ). Â òàêèõ ðàññóæ-
äåíèÿõ èíôîðìàöèÿ ðàñïðîñòðàíÿåòñÿ ïî ñòðóêòóðå ìîäåëè ÷åðåç ñåïàðàòîðû.
À èìåííî, åñëè y — öåëåâàÿ ïåðåìåííàÿ, à ïåðåìåííàÿ x âõîäèò â ñîñòàâ ñâèäåò-
åëüñòâà, òî (ïðè òî÷íîì âûâîäå) èíôîðìàöèÿ áóäåò ïðîõîäèòü ÷åðåç êàæäóþ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 29
Ðèñ. 4
âåðøèíó z S x y� lom ( , ) êàæäîãî ëîêàëüíî-ìèíèìàëüíîãî ñåïàðàòîðà S x ylom ( , ).
Ïîñêîëüêó ïðåäëîæåííûé èíñòðóìåíòàðèé â ïåðâóþ î÷åðåäü ïðåäíàçíà÷åí
äëÿ ìåòîäîâ âûâîäà ñòðóêòóðû ìîäåëè èç ñòàòèñòè÷åñêèõ äàííûõ, åãî íóæíî íà-
ñòðîèòü äëÿ ýòèõ öåëåé. Ãðàôîâûå ïðåäèêàòû ñëåäóåò çàìåíèòü ýìïèðè÷åñêèìè
«äâîéíèêàìè» (counterparts) ñîãëàñíî ýêâèâàëåíòíîñòè (3). Îäíàêî ïðè ïðàêòè-
÷åñêîì èñïîëüçîâàíèè ýìïèðè÷åñêèõ âåðñèé ââåäåííûõ óòâåðæäåíèé è ïðàâèë
âîçíèêíóò òðóäíîñòè ââèäó ïðîáëåìàòè÷íîñòè ïîëíîé âåðñèè ïðåäïîëîæåíèÿ
íåîáìàí÷èâîñòè (2). Ïðåäëîæåííûå óòâåðæäåíèÿ è ïðàâèëà áîëåå òîíêèå, ÷åì
áîëüøèíñòâî èçâåñòíûõ. Îíè õàðàêòåðèçóþò îäíè ñåïàðàòîðû íà îñíîâå çíàíèé
äðóãèõ ñåïàðàòîðîâ è çàâèñèìîñòåé è îïèðàþòñÿ íà áîëåå ñòðîãèå âåðñèè ïðåä-
ïîëîæåíèÿ íåîáìàí÷èâîñòè, ÷åì (3) è (4).  ÷àñòíîñòè, ýìïèðè÷åñêèå «äâîéíè-
êè» óòâåðæäåíèé 1, 2à, 7 è ôàêòîâ 5, 6, 10–13, 15 îïèðàþòñÿ íà ñâîéñòâà ïóòåé (à
íå òîëüêî ðåáåð) è òðåáóþò âûïîëíåíèÿ ïðåäïîëîæåíèÿ íåîáìàí÷èâîñòè â çíà-
÷èòåëüíî áîëüøåì îáúåìå, ÷åì (4). Ïîýòîìó ïðÿìîëèíåéíîå ïðèìåíåíèå ýìïè-
ðè÷åñêèõ «äâîéíèêîâ» ïðàâèë ïðè âûâîäå èç íåáîëüøîé âûáîðêè äàííûõ ìîæåò
ïðèâåñòè ê ïîòåðå ñåïàðàòîðîâ è èäåíòèôèêàöèè ëîæíûõ ðåáåð. Îäíàêî ðèñê
îãðàíè÷èâàåòñÿ áëàãîäàðÿ òîìó, ÷òî èñïîëüçóþòñÿ (êàê ïðèçíàêè) îòíîøåíèÿ
(íå)çàâèñèìîñòè òîëüêî íóëåâîãî è ïåðâîãî ïîðÿäêà.
Ïðåäïîëîæåíèå íåîáìàí÷èâîñòè ìîæåò íàðóøàòüñÿ äàæå â ñëó÷àå î÷åíü áîëü-
øîé (àñèìïòîòè÷åñêîé) âûáîðêè äàííûõ. Èçâåñòíû ïðèìåðû ìîäåëåé, â êîòîðûõ
äàæå áàçîâûé ïðèíöèï (4) äàåò îøèáêè. Íà ïðàêòèêå ÷àñòî âûáîðêà äàííûõ — íå-
áîëüøàÿ èëè ìàëàÿ. Òîãäà âûáîðî÷íîå ðàñïðåäåëåíèå ìîæåò çíà÷èòåëüíî îòêëî-
íÿòüñÿ îò ãåíåðàòèâíîãî. Â ðåçóëüòàòå ðàñøèðÿåòñÿ ñôåðà íàðóøåíèÿ ïðåäïîëîæå-
íèÿ íåîáìàí÷èâîñòè. Óâåëè÷åíèå êàðäèíàëüíîñòè óñëîâèé òåñòîâ íåçàâèñèìîñòè
åùå áîëüøå îáîñòðÿåò ïðîáëåìó íåíàäåæíîñòè.
Ýìïèðè÷åñêèé ôàêò çàâèñèìîñòè — áîëåå óäîáíîå ñâèäåòåëüñòâî äëÿ âûâî-
äîâ, ÷åì ýìïèðè÷åñêàÿ íåçàâèñèìîñòü.  ÷àñòíîñòè, � � �Pr ( )x y åñòü äîâîëüíî
ðîáàñòíîå ñâèäåòåëüñòâî ñóùåñòâîâàíèÿ öåïè. Èìïëèêàöèÿ � � � �Pr ( )x yS
� � � �Ds ( )x yS âåðíà, à èìïëèêàöèÿ Pr ( )x y� � �S Ds ( )x y� �S — íåò.
Ýìïèðè÷åñêàÿ íåçàâèñèìîñòü íå ãàðàíòèðóåò îòñóòñòâèÿ öåïè, íî ñâèäåòåëüñòâó-
åò î ñëàáîñòè (âîçìîæíîé) çàâèñèìîñòè. Äîâîëüíî íàäåæíà ðåäóöèðîâàííàÿ âåð-
ñèÿ: Pr ( ) ( — )x y x y� � � �S .
Íàäåæíîñòü âûâîäà íà îñíîâå ýìïèðè÷åñêèõ ñâèäåòåëüñòâ ìîæíî ïîâûñèòü
çà ñ÷åò êîíòðàñòíûõ òåñòîâ çàâèñèìîñòè-íåçàâèñèìîñòè:
• Pr Pr( ) & ( )z x y z y� � � � � — àêòóàëüíàÿ 1-ñåïàðàöèÿ [15].
• Pr Pr( ) & ( )z y z x y� � � � � — ïðîâîêàöèÿ çàâèñèìîñòè [13].
Áëàãîäàðÿ àêòóàëüíîé ñåïàðàöèè ìîæíî èçáåæàòü îøèáî÷íîãî îòñòðàíåíèÿ
âåðøèíû â ñèòóàöèÿõ òèïà «ñëàáàÿ ïðîâîöèðîâàííàÿ çàâèñèìîñòü», ÷òî ìîæíî
ïðîèëëþñòðèðîâàòü ñëåäóþùèì ïðèìåðîì. Ïóñòü èìååì ãàóññîâó ñåòü,
îïèñûâàåìóþ óðàâíåíèÿìè:
x w z x w � �� � �1 2 30 8; ; , ;
y z aw � �0 7 4, � .
Ïóñòü âñå ÷ëåíû îøèáîê � i âçàèìíî íåçàâèñèìû è èìåþò ñòàíäàðòíîå îòêëî-
íåíèå � 2. Â ýòîé ìîäåëè åäèíñòâåííûì ñåïàðàòîðîì äëÿ ( , )x y ÿâëÿåòñÿ
{ }z w, . Ñîãëàñíî ôàêòó 13 áóäåò � � �Ds ( )x y w , ïîýòîìó w íå äîëæíà îòñòðà-
íÿòüñÿ. Íî â íåáîëüøèõ âûáîðêàõ îøèáêà îòñòðàíåíèÿ âîçìîæíà. Ïðåäóñëîâè-
åì òàêîé îøèáêè ÿâëÿåòñÿ îïðåäåëåííûé íàáîð ñîîòíîøåíèé äëÿ âûáîðî÷íûõ
çíà÷åíèé êîýôôèöèåíòîâ êîððåëÿöèè, à èìåííî, äîëæíî áûòü: � � � �� �xw y wy| � .
Êðîìå òîãî, äîëæíî áûòü: � � � �� �xw y xy| � ; � � � �� �xw y xy z| |� ; � � � �� �xw y wz| � ;
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
� � � �� �xw y xz| � ; � � � �� �xw y zy| � . Ïðè óêàçàííûõ â óðàâíåíèÿõ çíà÷åíèÿõ ïàðà-
ìåòðîâ ýòè íåðàâåíñòâà âûïîëíÿþòñÿ äëÿ � � � �135 0 29, ,a . Ïðåäïîëîæèì,
ñòðóêòóðàëüíûå êîýôôèöèåíòû èìåþò èìåííî òàêèå âûáîðî÷íûå çíà÷å-
íèÿ, êàê çàïèñàíî âûøå, è ïðè ýòîì a � 0 9, . Òîãäà ïîëó÷èì ñëåäóþ-
ùèå âûáîðî÷íûå îöåíêè çíà÷åíèé êîýôôèöèåíòîâ (÷àñòíîé) êîððåëÿöèè:
� xw y| , 0133; � wy � 0 235, ; � xy 0 484, ; � xz 0 615, ; � zy 0 480, ; � wz 0 492, ;
� xy z| 0 272, . Ëåãêî ïðåäñòàâèòü, ÷òî, ïðè îïðåäåëåííîì ðàçìåðå âûáîðêè,
â ðåçóëüòàòå òåñòèðîâàíèÿ áóäåò ïðèíÿòà íåçàâèñèìîñòü Pr ( )x y w� � (ñèí-
äðîì ñëàáîé ïðîâîöèðîâàííîé çàâèñèìîñòè), â òî âðåìÿ êàê äëÿ îñòàëüíûõ
ïåðå÷èñëåííûõ îòíîøåíèé — íåò. Òîãäà ïåðåìåííàÿ w áóäåò èñêëþ÷åíà èç
÷èñëà êàíäèäàòîâ â ñåïàðàòîð è ïîòåðÿåòñÿ åäèíñòâåííûé ñåïàðàòîð.
(Ðàçóìååòñÿ, ýòî óïðîùåííîå îáúÿñíåíèå. Äëÿ êîððåêòíîñòè íóæíî ñðàâíèâàòü
çíà÷åíèÿ z-ñòàòèñòèêè Ôèøåðà.)
Âåðñèÿ (7) ïðàâèëà çàùèòèò îò îøèáêè â îïèñàííîé ñèòóàöèè. Ýòî îáúÿñíÿ-
åò öåëåñîîáðàçíîñòü óñèëåíèÿ ïðàâèëà «îòñòðàíåíèÿ» èíñòðóìåíòîì àêòóàëüíîé
ñåïàðàöèè.
Íàäåæíîñòü ýìïèðè÷åñêîé âåðñèè «îòñòðàíåíèÿ» (7) ìîæíî àðãóìåíòèðî-
âàòü ñëåäóþùèì îáðàçîì [12]. Ôàêòû Ds Ds( ) & ( )z x y z y� � � � � ñâèäåò-
åëüñòâóþò, ÷òî ïîñëå çàêðûòèÿ öåïåé ÷åðåç âåðøèíó x óæå íå îñòàåòñÿ ñèëüíûõ
öåïåé ìåæäó âåðøèíàìè y è z. Òîãäà ìîæíî çàêëþ÷èòü, ÷òî âñå âîçìîæíûå öåïè
ìåæäó âåðøèíàìè y è x, èäóùèå ÷åðåç z, áóäóò åùå ñëàáåå, ïîñêîëüêó âêëþ÷àþò
â ñåáÿ óêàçàííûå ñëàáûå öåïè êàê ÷àñòü. Îäíàêî ýòà àðãóìåíòàöèÿ íå ó÷èòûâàåò
âçàèìîäåéñòâèÿ ïóòåé, òàê ÷òî ïðè ìàëûõ âûáîðêàõ äàííûõ è íåóäà÷íûõ
ñî÷åòàíèÿõ ïàðàìåòðîâ ðèñê îøèáêè îñòàåòñÿ.
Íåíàäåæíîé áóäåò ýìïèðè÷åñêàÿ âåðñèÿ ïðàâèëà «÷óæîãî ãåíà» (ñì.
ôàêò 11). Íî ñ ïîìîùüþ ïðîâîêàöèè çàâèñèìîñòè ìîæíî ïîëó÷èòü äîâîëüíî íàä-
åæíîå ïðàâèëî èäåíòèôèêàöèè îáîþäîáëèçêîé êîëëàéäåðíîé âåðøèíû
(non-ancestral common covariate):
� � � � � � � �w w z w x w z x:[ ( ) & ( ) & ( ) &Pr Pr Pr
& ( ) & ( )] ( , )Pr Pr lomw y w z y z S x y� � � � � � � . (9)
Ñ ïîìîùüþ (9) äëÿ ïðèìåðà íà ðèñ. 4 âåðøèíû u è w ìîæíî èäåíòèôèöèðî-
âàòü êàê «÷óæèå ãåíû» äëÿ âåðøèí x è y è èñêëþ÷èòü q è z èç ïîèñêà
ñåïàðàòîðà.
Îòìåòèì, ÷òî ïðåäëîæåííûå èíñòðóìåíòû ïðåäîñòàâëÿþò âîçìîæíîñòè â
ïðîöåññå âûâîäà êîìáèíèðîâàòü àïðèîðíûå çíàíèÿ (î ôðàãìåíòàõ ãðàôà) è ýìïè-
ðè÷åñêèå ñâèäåòåëüñòâà [12].
ÇÀÊËÞ×ÅÍÈÅ
Óñòàíîâëåíû íåîáõîäèìûå òðåáîâàíèÿ ê ÷ëåíàì ñåïàðàòîðîâ, à òàêæå ïðèçíà-
êè ñóùåñòâîâàíèÿ èëè îòñóòñòâèÿ ðåáåð. Äàííûå òðåáîâàíèÿ ê ÷ëåíàì ñåïàðà-
òîðîâ ïîçâîëÿþò îòñåÿòü íåêîòîðûõ êàíäèäàòîâ â ñåïàðàòîð è òåì ñàìûì
óïðîñòèòü çàäà÷ó èäåíòèôèêàöèè ñòðóêòóðû ìîäåëè. Ïðåäëîæåííûå è îáîñíî-
âàííûå óòâåðæäåíèÿ è ïðàâèëà ïîçâîëÿþò (àäàïòèâíî) îïòèìèçèðîâàòü ïîèñê
ñåïàðàòîðîâ â ïðîöåññå àíàëèçà èëè ñèíòåçà ÀÎÃ-ìîäåëåé. Ýòè ñðåäñòâà
èìåþò ñëåäóþùèå ïðåèìóùåñòâà:
• óñêîðÿþò è óïðîùàþò èäåíòèôèêàöèþ ñóùåñòâîâàíèÿ èëè îòñóòñòâèÿ
ðåáåð;
• ñïîñîáñòâóþò ðàííåìó ñîêðàùåíèþ ñïèñêîâ êàíäèäàòîâ â ñåïàðàòîðû;
• îáåñïå÷èâàþò âûÿâëåíèå ìèíèìàëüíûõ ñåïàðàòîðîâ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 31
• ñïîñîáñòâóþò óìåíüøåíèþ ÷èñëà òåñòîâ íåçàâèñèìîñòè ïðè âûâîäå èç
äàííûõ;
• ñïîñîáñòâóþò ñíèæåíèþ ïîðÿäêà (ðàíãà) òåñòîâ óñëîâíîé íåçàâèñèìîñòè è
óïðîùåíèþ çàïðîñîâ ê áàçå äàííûõ;
• ïîääåðæèâàþò èñïîëüçîâàíèå àïðèîðíûõ çíàíèé î ñòðóêòóðå ìîäåëè ïðè
îêîí÷àòåëüíîì âûâîäå ñòðóêòóðû ÀÎÃ-ìîäåëè.
 ðàáîòå ïîêàçàíû íîâûå âîçìîæíîñòè è àíàëèòè÷åñêèå ñðåäñòâà, êîòîðûå
ïîâûøàþò ýôôåêòèâíîñòü èíäóêòèâíîãî âûâîäà ñòðóêòóð âåðîÿòíîñòíûõ
ìîäåëåé çàâèñèìîñòåé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. P e a r l J . Probabilistic reasoning in intelligent systems: networks of plausible inference. — San
Mateo: Morgan Kaufmann, 1988. — 552 p.
2. S c h e i n e s R . , S p i r t e s P . , G l y m o u r C . e t a l . The TETRAD project: Constraint
based aids to causal model specification // Multivar. Behavior. Res. — 1998. — 33, N 1. — P.
65–118.
3. N e a p o l i t a n R . E . Learning Bayesian networks. — Englewood Cliffs: Prentice Hall, 2003. —
674 p.
4. P e a r l J . Causality: models, reasoning, and inference. — Cambridge: Cambridge Univ. Press,
2000. — 526 p.
5. S c h e i n e s R . , S p i r t e s P . , G l y m o u r C . , M e e k C . TETRAD II: Tools for discov-
ery. — Hillsdale, NJ: Lawrence Erlbaum Assoc., 1994.
6. V e r m a T . , P e a r l J . Causal networks: semantics and expressiveness / R. Shachter,
T.S. Levitt, L.N. Kanal (Eds.) // Uncertainty in Artificial Intelligence. — Amsterdam: Elsevier Sci.
Publ., North-Holland, 1990. — 4. — P. 69–76.
7. S c h e i n e s R . An introduction to causal inference // Causality in Crisis? / V. McKim and
S. Turner (Eds.). — Notre Dame: Univ. of Notre Dame Press, 1997. — P. 185–200.
8. À í ä î í Ô . È . , Á à ë à á à í î â À . Ñ . Ñòðóêòóðíûå ñòàòèñòè÷åñêèå ìîäåëè: èíñòðóìåíò
ïîçíàíèÿ è ìîäåëèðîâàíèÿ // Ñèñòåì. äîñë³ä. òà ³íôîðì. òåõíîëî㳿. — 2007. — ¹ 1. — Ñ.
79–98.
9. C h i c k e r i n g D . M . , M e e k C . , H e c k e r m a n D . Large-sample learning of Bayesian
networks is NP-hard // Proc. of 19th Conf. on Uncertainty in Artificial Intelligence. — Acapulco,
Mexico: Morgan Kaufmann, 2003. — P. 124–133.
10. M e e k C . Strong-completeness and faithfulness in belief networks / S. Hanks, P. Besnard (Eds.) //
Proc. of the 11th Conf. on Uncertainty in Artificial Intelligence (Montreal, QU). — San Mateo, CA:
Morgan Kaufmann, 1995. — P. 411–418.
11. Á à ë à á à í î â A . C . Âîññòàíîâëåíèå ñòðóêòóð ñèñòåì âåðîÿòíîñòíûõ çàâèñèìîñòåé èç
äàííûõ. Àïïàðàò ãåíîòèïîâ ïåðåìåííûõ // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2003. —
¹ 2. — C. 91–99. (see: http://www.begellhouse.com/journals/)
12. Á à ë à á à í î â Î . Ñ . Ïðàâèëà ïŸäáîðó ñåïàðàòîðŸâ ó áàºñ³âñüêèõ ìåðåæàõ // Ïðîáëåìè
ïðîãðàìóâàííÿ. — 2007. — ¹ 4. — Ñ. 22–33.
13. Á à ë à á à í î â A . C . Ê âûâîäó ñòðóêòóð ìîäåëåé âåðîÿòíîñòíûõ çàâèñèìîñòåé èç
ñòàòèñòè÷åñêèõ äàííûõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 5. — Ñ. 19–31.
14. T i a n J . , P a z A . , P e a r l J . Finding minimal d-separators: Techn. Rep. / UCLA, Computer
Sci. Dep, CA. — R-254. — Los Angeles, 1998. — 15 p.
15. Á à ë à á à í î â À . Ñ . Èíäóêòèâíûé ìåòîä âîññòàíîâëåíèÿ ìîíîïîòîêîâûõ âåðîÿòíîñòíûõ
ãðàôîâûõ ìîäåëåé çàâèñèìîñòåé // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2003. — ¹ 5. —
C. 75–84.
Ïîñòóïèëà 26.06.2008
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
|