Укрытие (теория графов)

Поделись знанием:
Перейти к: навигация, поиск

В теории графов укрытие — это определённый тип функции на множествах вершин неориентированного графа. Если укрытие существует, его может использовать беглец, чтобы выиграть игру преследование-уклонение[en] на графе путём использования этой функции на каждом шаге игры для определения безопасных множеств вершин, куда можно перейти. Укрытия были впервые введены Сеймуром и Томасом[1] как средство характеризации древесной ширины графов[2]. Другие приложения этого понятия — доказательство существования малых сепараторов в замкнутых по минорам семействах графов[3] и описание краёв[en] и миноров клик бесконечных графов[4][5].





Определение

Если G — неориентированный граф, а X — множество вершин, то X-борт — это непустая связная компонента подграфа графа G, образованная удалением X. Укрытие порядка k в графе G — это функция β, отображающая любое множество X с менее чем k вершинами в X-борт β(X). Эта функция должна также удовлетворять дополнительным ограничениям, которые определяются различным образом различными авторами. Число k называется порядком укрытием[6].

В первоначальном определении Сеймура и Томаса[2] укрытия требуется выполнение свойства, что любые два борта β(X) и β(Y) должны касаться друг друга — либо они должны иметь общую вершину, либо должно существовать ребро, концы которого принадлежат этим двум бортам. В определении, использованном позднее Алоном, Сеймуром и Томасом[3], для укрытия требуется удовлетворение более слабого свойства монотонности — если X ⊆ Y и оба множества, как X, так и Y, имеют меньше, чем k вершин, то β(Y) ⊆ β(X). Из свойства касания вытекает свойство монотонности, но обратное будет выполняться не обязательно. Однако из результатов Сеймура и Томаса следует[2], что в конечных графах, если укрытие со свойством монотонности существует, то существует укрытие с тем же порядком и свойством касания.

Укрытия с определением касания тесно связаны с ежевиками, семействами связных подграфов заданного графа, касающихся друг друга. Порядок ежевики — это минимальное число вершин, необходимых во множестве вершин, которое имеет представителя в каждом подграфе семейства. Множество бортов β(X) для укрытия порядка k (с определением касания) образует ежевику порядка как минимум k, поскольку любое множество Y с числом вершин, меньшим k не может покрыть подграф β(Y). Обратно — из любой ежевики порядка k, можно построить укрытие того же порядка путём определения β(X) (для каждого X) как X-борта, который включает все подграфы в ежевике, не имеющие общих точек с  X. Требование, что подграфы в ежевике касаются друг друга, может быть использован для того, чтобы показать, что такой X-борт существует, и что все борты β(X), выбранные таким способом, касаются друг другом. Таким образом, у графа есть ежевика порядка k тогда и только тогда, когда у него есть укрытие порядка k.

Пример

В качестве примера: пусть G — решётка с девятью вершинами. Определим укрытие порядка 4 в G, отобразив каждое множество X с тремя и менее вершинами в X-борт β(X) следующим образом:

  • Если существует уникальный X-борт, который больше любого другого X-борта, пусть β(X) будет этим уникальным большим X-бортом.
  • В противном случае, выберем в качестве β(X) произвольный X-борт.

Легко напрямую проверить с помощью разбора случаев[en], что эта функция β удовлетворяет свойствам монотонности укрытия. Если X ⊆ Y и X имеет менее двух вершин, или X состоит из двух вершин, которые не являются двумя соседями угловой вершины решётки, то существует только один X-борт и он содержит любой Y-борт. В оставшемся случае X состоит из двух соседей угловой вершины и имеет два X-борта — один состоит из угловой вершины, а другой (выбираемый в качестве β(X)) состоит из шести оставшихся вершин. Не имеет значения, какая вершина добавлена в X для образования Y, будет существовать Y-борт, по крайней мере, с четырьмя вершинами, который должен быть уникальным наибольшим бортом, поскольку он содержит более половины вершин не из Y. Этот большой Y-борт будет выбран в качестве β(Y) и будет подмножеством β(X). Таким образом, в любом случае свойство монотонности выполняется.

Преследование-уклонение

Укрытия моделируют определённые классы стратегий для беглеца в игре преследования-уклонения[en], в которой меньше, чем k, преследователей пытаются схватить одного беглеца. Положения как преследователей, так и беглеца ограничены вершинами заданного неориентированного графа, а позиции и преследователей и беглеца известны обоим игрокам. На каждом ходе игры может быть добавлен новый преследователь в произвольную вершину графа (пока не достигнем величины в k преследователей) или один из уже существующих преследователей может быть удалён с графа. Однако до добавления нового преследователя беглец получает информацию, куда будет добавлен преследователь, и может передвигаться по рёбрам графа в любую незанятую вершину. Во время движения беглец не может проходить через вершину, занятую одним из преследователей.

Если k- укрытие (со свойством монотонности) существует, то беглец может избегать поимки бесконечно долго и тем самым выиграть, если всегда будет двигаться к вершине β(X), где X — множество вершин, занятых преследователями к концу хода. Свойство монотонности укрытия гарантирует, что при добавлении нового преследователя в вершину графа вершины в β(X) всегда будут доступны из текущего положения беглеца[2].

Например, беглец выигрывает эту игру против трёх преследователей на решётке 3 × 3 с помощью описанной стратегии, опираясь на укрытие порядка 4, описанное в примере. Однако в той же самой игре четыре преследователя всегда могут поймать беглеца, разместив преследователей в три вершины, которые разрезают решётку на два пути с тремя вершинами в каждом. Затем размещаем преследователя в центр пути, содержащего беглеца, и, наконец, удаляем одного преследователя, который не смежен с углом, и помещаем его на беглеца. Таким образом, решётка 3 × 3 не имеет укрытия порядка 5.

Укрытия со свойством касания позволяют беглецу выиграть против более сильных преследователей, которые могут одновременно прыгать с одной позиции в другую[2].

Связь с древесной шириной, сепараторами и минорами

Укрытия могут быть использованы для описания древесной ширины графа — граф имеет укрытие порядка k тогда и только тогда, когда он имеет древесную ширину по меньшей мере k − 1. Древесная декомпозиция может быть использована для описания выигрышной стратегии для преследователей в той же игре преследования-уклонения, так что верно утверждение, что граф имеет укрытие порядка k тогда и только тогда, когда беглец выигрывает при правильной игре против менее чем k преследователей. В играх, выигрываемых беглецом, всегда существует оптимальная стратегия в виде укрытия, а в играх, выигрываемых преследователями, всегда существует оптимальная стратегия в виде древесной декомпозиции[2]. Например, поскольку решётка 3 × 3 имеет укрытие порядка 4, но не имеет укрытия порядка 5, она должна иметь древесную ширину, в точности равную 3. Та же минимаксная теорема может быть обобщена на бесконечные графы с конечной древесной шириной, если в определении древесной ширины от лежащего в основе дерева требуется отсутствие концов[en][2].

Укрытия также тесно связаны с существованием сепараторов[en], малого размера множеств вершин X в графе с n вершинами, такого, что любой X-борт имеет максимум 2n/3 вершин. Если граф G не имеет сепаратора с k вершинами, то любое множество X с максимум k вершинами имеет (уникальный) X-борт с более чем 2n/3 вершинами. В этом случае G имеет укрытие порядка k + 1, в котором β(X) определяется как уникальный большой X-борт. То есть любой граф имеет либо малый сепаратор, либо укрытие высокого порядка[3].

Если граф G имеет укрытие порядка k, при k ≥ h3/2n1/2 для некоторого целого h, тогда G должен также иметь полный граф Kh в качестве минора. Другими словами, число Хадвигера графа с n вершинами с укрытием порядка k имеет значение, не меньшее k2/3n−1/3. Как следствие, свободные от Kh миноров графы имеют древесную ширину, меньшую h3/2n1/2 и сепараторы размера, меньшего h3/2n1/2. Более обще, граница O(√n) древесной ширины и размер сепаратора выполняется для любого нетривиального семейства графов, которые могут быть охарактеризованы запрещёнными графами, поскольку для любого такого семейства существует константа h, такая, что семейство не включает Kh[3].

В бесконечных графах

Если граф G содержит луч, полубесконечный простой путь, имеющий начальную вершину, но не имеющий конечной вершины, то он имеет укрытие порядка ℵ0[en], то есть функцию β, которая отображает каждое конечное множество X вершин в X-борт, удовлетворяющую условиям укрытий. А именно, определим β(X) как уникальный X-борт, который состоит из неограниченного числа вершин луча. Таким образом, в случае бесконечных графов связь между древесной шириной и укрытиями ломается — отдельный луч, несмотря на то, что он сам по себе является деревом, имеет укрытия всех конечных порядков и даже более сильно, укрытие порядка ℵ0. Два луча бесконечного графа считаются эквивалентными, если нет конечного множества вершин, которые разделяют бесконечно много вершин одного луча от бесконечно большого числа вершин другого луча. Это отношение эквивалентности и его отношения эквивалентности называются концами[en] графа.

Концы любого графа имеют один-к-одному соответствие с укрытиями порядка ℵ0. Любой луч определяет укрытие и любые два эквивалентных луча определяют то же самое укрытие [4]. В обратную сторону — любое укрытие определяется лучами таким способом, что можно показать следующим анализом вариантов:

  • Если укрытие имеет свойство, что пересечение <math>S=\bigcap_X\left(\beta(X)\cup X\right)</math> (где пересечение пробегает по всем конечным множествам X) является само по себе бесконечным множеством S, то любой конечный простой путь, который имеет конечную вершину в S, может быть расширен дополнительной вершиной из S, и повторение процесса расширения даёт луч, проходящий через бесконечное число вершин из S. Это луч определяет заданную укрытие.
  • С другой стороны, если S конечно, то (работая с подграфом G \ S) его можно считать пустым. В этом случае для любого конечного множества Xi вершин существует множество Xi + 1 со свойством, что Xi не имеет общих элементов с <math>X_{i+1}\cup\beta(X_{i+1})</math>. Если грабитель следует стратегии уклонения, определяемой укрытием, а полиция следует стратегии, задаваемой этой последовательностью множеств, то путь, по которому следует грабитель, образует луч, который определяет укрытие[5].

Таким образом, любой класс эквивалентности лучей определяет уникальное укрытие, а любая укрытое определяется классом эквивалентности лучей.

Для любого кардинального числа <math>\kappa\ge\aleph_1</math>, бесконечный граф G имеет укрытие порядка κ тогда и только тогда, когда он имеет минор клики порядка κ. То есть для несчётных кардинальных чисел, наибольший порядок укрытия в G является числом Хадвигера графа G[4].

Напишите отзыв о статье "Укрытие (теория графов)"

Примечания

  1. ↑ Seymour, Thomas, 1993.
  2. ↑ 1 2 3 4 5 6 7 Seymour, Thomas, 1993, с. 22–33.
  3. ↑ 1 2 3 4 Alon, Seymour, Thomas, 1990, с. 801–808.
  4. ↑ 1 2 3 Robertson, Seymour, Thomas, 1991, с. 303–319.
  5. ↑ 1 2 Diestel, Kühn, 2003, с. 197–206.
  6. ↑ Johnson, Robertson, Seymour, Thomas, 2001, с. 138–155.

Литература

<imagemap>: неверное или отсутствующее изображение

 Для улучшения этой статьи желательно?:

Отрывок, характеризующий Укрытие (теория графов)

– Я рад, я рад, – проговорил он и, пристально еще взглянув ей в глаза, быстро отошел и сел на свое место. – Садитесь, садитесь! Михаил Иванович, садитесь.
Он указал невестке место подле себя. Официант отодвинул для нее стул.
– Го, го! – сказал старик, оглядывая ее округленную талию. – Поторопилась, нехорошо!
Он засмеялся сухо, холодно, неприятно, как он всегда смеялся, одним ртом, а не глазами.
– Ходить надо, ходить, как можно больше, как можно больше, – сказал он.
Маленькая княгиня не слыхала или не хотела слышать его слов. Она молчала и казалась смущенною. Князь спросил ее об отце, и княгиня заговорила и улыбнулась. Он спросил ее об общих знакомых: княгиня еще более оживилась и стала рассказывать, передавая князю поклоны и городские сплетни.
– La comtesse Apraksine, la pauvre, a perdu son Mariei, et elle a pleure les larmes de ses yeux, [Княгиня Апраксина, бедняжка, потеряла своего мужа и выплакала все глаза свои,] – говорила она, всё более и более оживляясь.
По мере того как она оживлялась, князь всё строже и строже смотрел на нее и вдруг, как будто достаточно изучив ее и составив себе ясное о ней понятие, отвернулся от нее и обратился к Михайлу Ивановичу.
– Ну, что, Михайла Иванович, Буонапарте то нашему плохо приходится. Как мне князь Андрей (он всегда так называл сына в третьем лице) порассказал, какие на него силы собираются! А мы с вами всё его пустым человеком считали.
Михаил Иванович, решительно не знавший, когда это мы с вами говорили такие слова о Бонапарте, но понимавший, что он был нужен для вступления в любимый разговор, удивленно взглянул на молодого князя, сам не зная, что из этого выйдет.
– Он у меня тактик великий! – сказал князь сыну, указывая на архитектора.
И разговор зашел опять о войне, о Бонапарте и нынешних генералах и государственных людях. Старый князь, казалось, был убежден не только в том, что все теперешние деятели были мальчишки, не смыслившие и азбуки военного и государственного дела, и что Бонапарте был ничтожный французишка, имевший успех только потому, что уже не было Потемкиных и Суворовых противопоставить ему; но он был убежден даже, что никаких политических затруднений не было в Европе, не было и войны, а была какая то кукольная комедия, в которую играли нынешние люди, притворяясь, что делают дело. Князь Андрей весело выдерживал насмешки отца над новыми людьми и с видимою радостью вызывал отца на разговор и слушал его.
– Всё кажется хорошим, что было прежде, – сказал он, – а разве тот же Суворов не попался в ловушку, которую ему поставил Моро, и не умел из нее выпутаться?
– Это кто тебе сказал? Кто сказал? – крикнул князь. – Суворов! – И он отбросил тарелку, которую живо подхватил Тихон. – Суворов!… Подумавши, князь Андрей. Два: Фридрих и Суворов… Моро! Моро был бы в плену, коли бы у Суворова руки свободны были; а у него на руках сидели хофс кригс вурст шнапс рат. Ему чорт не рад. Вот пойдете, эти хофс кригс вурст раты узнаете! Суворов с ними не сладил, так уж где ж Михайле Кутузову сладить? Нет, дружок, – продолжал он, – вам с своими генералами против Бонапарте не обойтись; надо французов взять, чтобы своя своих не познаша и своя своих побиваша. Немца Палена в Новый Йорк, в Америку, за французом Моро послали, – сказал он, намекая на приглашение, которое в этом году было сделано Моро вступить в русскую службу. – Чудеса!… Что Потемкины, Суворовы, Орловы разве немцы были? Нет, брат, либо там вы все с ума сошли, либо я из ума выжил. Дай вам Бог, а мы посмотрим. Бонапарте у них стал полководец великий! Гм!…
– Я ничего не говорю, чтобы все распоряжения были хороши, – сказал князь Андрей, – только я не могу понять, как вы можете так судить о Бонапарте. Смейтесь, как хотите, а Бонапарте всё таки великий полководец!
– Михайла Иванович! – закричал старый князь архитектору, который, занявшись жарким, надеялся, что про него забыли. – Я вам говорил, что Бонапарте великий тактик? Вон и он говорит.
– Как же, ваше сиятельство, – отвечал архитектор.
Князь опять засмеялся своим холодным смехом.
– Бонапарте в рубашке родился. Солдаты у него прекрасные. Да и на первых он на немцев напал. А немцев только ленивый не бил. С тех пор как мир стоит, немцев все били. А они никого. Только друг друга. Он на них свою славу сделал.
И князь начал разбирать все ошибки, которые, по его понятиям, делал Бонапарте во всех своих войнах и даже в государственных делах. Сын не возражал, но видно было, что какие бы доводы ему ни представляли, он так же мало способен был изменить свое мнение, как и старый князь. Князь Андрей слушал, удерживаясь от возражений и невольно удивляясь, как мог этот старый человек, сидя столько лет один безвыездно в деревне, в таких подробностях и с такою тонкостью знать и обсуживать все военные и политические обстоятельства Европы последних годов.
– Ты думаешь, я, старик, не понимаю настоящего положения дел? – заключил он. – А мне оно вот где! Я ночи не сплю. Ну, где же этот великий полководец твой то, где он показал себя?
– Это длинно было бы, – отвечал сын.
– Ступай же ты к Буонапарте своему. M lle Bourienne, voila encore un admirateur de votre goujat d'empereur! [вот еще поклонник вашего холопского императора…] – закричал он отличным французским языком.
– Vous savez, que je ne suis pas bonapartiste, mon prince. [Вы знаете, князь, что я не бонапартистка.]
– «Dieu sait quand reviendra»… [Бог знает, вернется когда!] – пропел князь фальшиво, еще фальшивее засмеялся и вышел из за стола.
Маленькая княгиня во всё время спора и остального обеда молчала и испуганно поглядывала то на княжну Марью, то на свекра. Когда они вышли из за стола, она взяла за руку золовку и отозвала ее в другую комнату.
– Сomme c'est un homme d'esprit votre pere, – сказала она, – c'est a cause de cela peut etre qu'il me fait peur. [Какой умный человек ваш батюшка. Может быть, от этого то я и боюсь его.]
– Ax, он так добр! – сказала княжна.


Князь Андрей уезжал на другой день вечером. Старый князь, не отступая от своего порядка, после обеда ушел к себе. Маленькая княгиня была у золовки. Князь Андрей, одевшись в дорожный сюртук без эполет, в отведенных ему покоях укладывался с своим камердинером. Сам осмотрев коляску и укладку чемоданов, он велел закладывать. В комнате оставались только те вещи, которые князь Андрей всегда брал с собой: шкатулка, большой серебряный погребец, два турецких пистолета и шашка, подарок отца, привезенный из под Очакова. Все эти дорожные принадлежности были в большом порядке у князя Андрея: всё было ново, чисто, в суконных чехлах, старательно завязано тесемочками.
В минуты отъезда и перемены жизни на людей, способных обдумывать свои поступки, обыкновенно находит серьезное настроение мыслей. В эти минуты обыкновенно поверяется прошедшее и делаются планы будущего. Лицо князя Андрея было очень задумчиво и нежно. Он, заложив руки назад, быстро ходил по комнате из угла в угол, глядя вперед себя, и задумчиво покачивал головой. Страшно ли ему было итти на войну, грустно ли бросить жену, – может быть, и то и другое, только, видимо, не желая, чтоб его видели в таком положении, услыхав шаги в сенях, он торопливо высвободил руки, остановился у стола, как будто увязывал чехол шкатулки, и принял свое всегдашнее, спокойное и непроницаемое выражение. Это были тяжелые шаги княжны Марьи.
– Мне сказали, что ты велел закладывать, – сказала она, запыхавшись (она, видно, бежала), – а мне так хотелось еще поговорить с тобой наедине. Бог знает, на сколько времени опять расстаемся. Ты не сердишься, что я пришла? Ты очень переменился, Андрюша, – прибавила она как бы в объяснение такого вопроса.
Она улыбнулась, произнося слово «Андрюша». Видно, ей самой было странно подумать, что этот строгий, красивый мужчина был тот самый Андрюша, худой, шаловливый мальчик, товарищ детства.
– А где Lise? – спросил он, только улыбкой отвечая на ее вопрос.
– Она так устала, что заснула у меня в комнате на диване. Ax, Andre! Que! tresor de femme vous avez, [Ax, Андрей! Какое сокровище твоя жена,] – сказала она, усаживаясь на диван против брата. – Она совершенный ребенок, такой милый, веселый ребенок. Я так ее полюбила.
Князь Андрей молчал, но княжна заметила ироническое и презрительное выражение, появившееся на его лице.
– Но надо быть снисходительным к маленьким слабостям; у кого их нет, Аndre! Ты не забудь, что она воспитана и выросла в свете. И потом ее положение теперь не розовое. Надобно входить в положение каждого. Tout comprendre, c'est tout pardonner. [Кто всё поймет, тот всё и простит.] Ты подумай, каково ей, бедняжке, после жизни, к которой она привыкла, расстаться с мужем и остаться одной в деревне и в ее положении? Это очень тяжело.
Князь Андрей улыбался, глядя на сестру, как мы улыбаемся, слушая людей, которых, нам кажется, что мы насквозь видим.
– Ты живешь в деревне и не находишь эту жизнь ужасною, – сказал он.
– Я другое дело. Что обо мне говорить! Я не желаю другой жизни, да и не могу желать, потому что не знаю никакой другой жизни. А ты подумай, Andre, для молодой и светской женщины похорониться в лучшие годы жизни в деревне, одной, потому что папенька всегда занят, а я… ты меня знаешь… как я бедна en ressources, [интересами.] для женщины, привыкшей к лучшему обществу. M lle Bourienne одна…
– Она мне очень не нравится, ваша Bourienne, – сказал князь Андрей.
– О, нет! Она очень милая и добрая,а главное – жалкая девушка.У нее никого,никого нет. По правде сказать, мне она не только не нужна, но стеснительна. Я,ты знаешь,и всегда была дикарка, а теперь еще больше. Я люблю быть одна… Mon pere [Отец] ее очень любит. Она и Михаил Иваныч – два лица, к которым он всегда ласков и добр, потому что они оба облагодетельствованы им; как говорит Стерн: «мы не столько любим людей за то добро, которое они нам сделали, сколько за то добро, которое мы им сделали». Mon pеre взял ее сиротой sur le pavе, [на мостовой,] и она очень добрая. И mon pere любит ее манеру чтения. Она по вечерам читает ему вслух. Она прекрасно читает.
– Ну, а по правде, Marie, тебе, я думаю, тяжело иногда бывает от характера отца? – вдруг спросил князь Андрей.
Княжна Марья сначала удивилась, потом испугалась этого вопроса.
– МНЕ?… Мне?!… Мне тяжело?! – сказала она.
– Он и всегда был крут; а теперь тяжел становится, я думаю, – сказал князь Андрей, видимо, нарочно, чтоб озадачить или испытать сестру, так легко отзываясь об отце.
– Ты всем хорош, Andre, но у тебя есть какая то гордость мысли, – сказала княжна, больше следуя за своим ходом мыслей, чем за ходом разговора, – и это большой грех. Разве возможно судить об отце? Да ежели бы и возможно было, какое другое чувство, кроме veneration, [глубокого уважения,] может возбудить такой человек, как mon pere? И я так довольна и счастлива с ним. Я только желала бы, чтобы вы все были счастливы, как я.
Брат недоверчиво покачал головой.
– Одно, что тяжело для меня, – я тебе по правде скажу, Andre, – это образ мыслей отца в религиозном отношении. Я не понимаю, как человек с таким огромным умом не может видеть того, что ясно, как день, и может так заблуждаться? Вот это составляет одно мое несчастие. Но и тут в последнее время я вижу тень улучшения. В последнее время его насмешки не так язвительны, и есть один монах, которого он принимал и долго говорил с ним.
– Ну, мой друг, я боюсь, что вы с монахом даром растрачиваете свой порох, – насмешливо, но ласково сказал князь Андрей.
– Аh! mon ami. [А! Друг мой.] Я только молюсь Богу и надеюсь, что Он услышит меня. Andre, – сказала она робко после минуты молчания, – у меня к тебе есть большая просьба.
– Что, мой друг?
– Нет, обещай мне, что ты не откажешь. Это тебе не будет стоить никакого труда, и ничего недостойного тебя в этом не будет. Только ты меня утешишь. Обещай, Андрюша, – сказала она, сунув руку в ридикюль и в нем держа что то, но еще не показывая, как будто то, что она держала, и составляло предмет просьбы и будто прежде получения обещания в исполнении просьбы она не могла вынуть из ридикюля это что то.
Она робко, умоляющим взглядом смотрела на брата.
– Ежели бы это и стоило мне большого труда… – как будто догадываясь, в чем было дело, отвечал князь Андрей.
– Ты, что хочешь, думай! Я знаю, ты такой же, как и mon pere. Что хочешь думай, но для меня это сделай. Сделай, пожалуйста! Его еще отец моего отца, наш дедушка, носил во всех войнах… – Она всё еще не доставала того, что держала, из ридикюля. – Так ты обещаешь мне?
– Конечно, в чем дело?
– Andre, я тебя благословлю образом, и ты обещай мне, что никогда его не будешь снимать. Обещаешь?
– Ежели он не в два пуда и шеи не оттянет… Чтобы тебе сделать удовольствие… – сказал князь Андрей, но в ту же секунду, заметив огорченное выражение, которое приняло лицо сестры при этой шутке, он раскаялся. – Очень рад, право очень рад, мой друг, – прибавил он.
– Против твоей воли Он спасет и помилует тебя и обратит тебя к Себе, потому что в Нем одном и истина и успокоение, – сказала она дрожащим от волнения голосом, с торжественным жестом держа в обеих руках перед братом овальный старинный образок Спасителя с черным ликом в серебряной ризе на серебряной цепочке мелкой работы.


Источник — «http://wiki-org.ru/wiki/index.php?title=Укрытие_(теория_графов)&oldid=79213060»