Комбинаторика многогранников

Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.

Исследования в комбинаторике многогранников распадаются на две ветви. Математики, работающие в этой области, изучают комбинаторику многогранников; например, они ищут неравенства, описывающие отношения между числом вершин, рёбер и граней разных размерностей в произвольном многограннике, а также изучают другие комбинаторные свойства многогранников, такие как связность и диаметр (число шагов, необходимых для достижения любой вершины из любой другой вершины). Кроме того, многие учёные, работающие в области информатики, используют фразу «комбинаторика многогранников» для описания исследований по точному описанию граней некоторых определённых многогранников (особенно, 0-1 многогранников, вершины которых являются подмножествами гиперкуба), возникающих из задач целочисленного программирования.

Грани и вектора подсчёта гранией

Грань выпуклого многогранника P можно определить как пересечение P и замкнутого полупространства H, такого, что граница H не содержит внутренних точек P. Размерность грани равна размерности этого пересечения. 0-мерные грани — это сами вершины, а 1-мерные грани (называются рёбрами) являются отрезками, соединяющими пары вершин. Заметим, что это определение включает в качестве граней пустые множества и весь многогранник P. Если P имеет размерность d, грани P с размерностью d − 1 называются фасками многогранника P, а грани размерности d − 2 называются гребнями. Грани P могут быть частично упорядочены по включению, образуя решётку граней, имеющую на вершине сам многогранник P и пустое множество внизу.

Ключевым методом комбинаторики многогранников является рассмотрение ƒ-вектора многогранника — вектора (f₀, f₁, …, f_d − 1), где f_i является числом i-мерных граней многогранника. Например, куб имеет восемь вершин, двенадцать рёбер и шесть граней (фасок), так что его ƒ-вектор равен (8,12,6). Двойственный многогранник имеет ƒ-вектор с тем же числами в обратном порядке. Так, например, правильный октаэдр, двойственный кубу, имеет ƒ-вектор (6,12,8). Расширенный ƒ-вектор образуется добавлением единиц к обоим концам ƒ-вектора, что соответствует перечислению объектов всех уровней решётки граней: f₋₁ = 1 отражает пустое множество в качестве грани, в то время как f_d = 1 отражает сам P. Для куба расширенный ƒ-вектор — это (1,8,12,6,1), а для октаэдра — (1,6,12,8,1). Хотя вектора этих примеров унимодальны (элементы слева направо сначала возрастают, а затем убывают), существуют многогранникы более высоких размерностей, для которых это неверно.

Для симплициальных политопов (политопов, у которых каждая грань является симплексом) часто преобразуют этот вектор, образуя h-вектор. Если мы рассматриваем элементы ƒ-вектора (без конечной 1) как коэффициенты многочлена ƒ(x) = Σf_ix^{d − i − 1} (например, для октаэдра это даёт многочлен ƒ(x) = x³ + 6x² + 12x + 8), тогда h-вектор содержит коэффициенты многочлена h(x) = ƒ(x − 1) (опять, для октаэдра, h(x) = x³ + 3x² + 3x + 1). Как пишет Циглер, «для различных задач о симплициальных политопах h-вектора много более удобны для задания информации о числе граней, чем f-вектора.»

Равенства и неравенства

Наиболее важное соотношение коэффициентов ƒ-вектора многогранника — это формула Эйлера Σ(−1)ⁱf_i = 0, где суммирование ведётся по элементам расширенного ƒ-вектора. В трёхмерном пространстве перенос двух единиц с левой и правой стороны расширенного ƒ-вектора (1, v, e, f, 1) в правую сторону равенства преобразует равенство к более привычному виду v − e + f = 2. Из того факта, что любая грань трёхмерного многогранника имеет по меньшей мере три ребра, следует, что 2e ≥ 3f . Используя это выражение для исключения e и f из формулы Эйлера, получим e ≤ 3v − 6 и f ≤ 2v − 4. Ввиду двойственности e ≤ 3f − 6 и v ≤ 2f − 4. Из теоремы Штайница следует, что любой 3-мерный целочисленный вектор, удовлетворяющий этим равенствам и неравенствам, является ƒ-вектором выпуклого многогранника.

В более высоких размерностях становятся важными и другие отношения между числом граней многогранника, включая уравнение Дена — Сомервиля, которое, выраженное в терминах h-векторов симплициальных политопов, принимает простую форму h_k = h_{d − k} для любого k. Вариант этих уравнений с k = 0 эквивалентен формуле Эйлера, но для d > 3 эти уравнения линейно независимы друг от друга и накладывают дополнительные ограничения на h-вектора (а потому и на ƒ-вектора).

Ещё одно важное неравенство для числа граней многогранника получается из теоремы о верхней оценке, впервые доказанной МакМалленом, которая утверждает, что d-мерный многогранник с n вершинами может иметь не больше граней какой-либо размерности, чем смежностный многогранник с тем же числом вершин:

<math>f_{k-1} \le \sum_{i=0}^{d/2} {}^* \left( \binom{d-i}{k-i}+\binom{i}{k-d+i} \right) \binom{n-d-1+i}{i},</math>

где звёздочка означает, что последний член суммы должен быть уменьшен вдвое, если d чётно. В асимптоте из этого следует, что не может быть более чем <math>\scriptstyle O(n^{\lfloor d/2\rfloor})</math> граней всех размерностей.

Даже для размерности четыре множество всех возможных ƒ-векторов выпуклых многогранников не образует выпуклое подмножество четырёхмерной целочисленной решётки и много остаётся неясным о возможных значениях этих векторов.

Свойства из теории графов

Наряду с числом граней многогранников исследователи изучают и другие их комбинаторные свойства, такие как свойства графов, получаемых из вершин и рёбер многогранников (их 1-скелета).

Теорема Балинского утверждает, что граф, полученный таким путём из любого d-мерного выпуклого многогранника, является вершинно d-связным. В случае трёхмерных многогранников это свойство и планарность может быть использовано для точного описания графов многогранников — теорема Штайница утверждает, что G является скелетом трёхмерного многогранника тогда и только тогда, когда G является вершинно 3-связным планарным графом.

Теорема Блайнда и Мани-Левицка (сформулированная как гипотеза Михой Перле (Micha Perles)) утверждает, что можно восстановить структуру граней простого многогранника по его графу. То есть, если данный неориентированный граф является скелетом простого многогранника, имеется только один многогранник (с точностью до комбинаторной эквивалентности), для которого граф служит скелетом. Это свойство находится в резком контрасте со свойствами смежностных (не простых) многогранников, графы которых являются полными — может существовать много различных смежностных многогранников с одним и тем же графом. Другое доказательство этой теоремы дал Калаи, а Фридман показал, как использовать эту теорему для создания алгоритма с полиномиальным временем для построения простых многогранников по их графам.

В контексте симплекс-метода линейного программирования важно учитывать диаметр многогранника, минимальное число вершин, которые необходимо пройти, чтобы достичь любую вершину из любой другой вершины. Система линейных неравенств задачи линейного программирования определяет грани многогранника допустимых решений задачи и симплекс-метод находит оптимальное решение, проходя путь по рёбрам этого многогранника. Таким образом, диаметр оценивает нижнюю границу числа шагов этого метода. Опровергнутая гипотеза Хирша давала сильную верхнюю оценку на диаметр. Известна более слабая (квазиполиномиальная) верхняя оценка диаметра, а гипотеза Хирша доказана для отдельных классов многогранников.

Вычислительные свойства

Определение того, ограничено ли число вершин заданного многогранника некоторым натуральным числом k, является трудной задачей и принадлежит классу сложности PP.

Грани 0-1 многогранников

Важно в контексте методов отсечений целочисленного программирования иметь возможность описать точно фаски (грани) многогранника, на которых лежат вершины, соответствующие решениям комбинаторных оптимизационных задач. Часто такие задачи имеют решения, которые можно задать битовыми векторами, а соответствующие многогранники имеют вершины, координатами которых служат числа нуль и единица.

В качестве примера возьмём многогранник Биркгофа, множество n × n матриц, которые можно образовать выпуклыми комбинациями матриц перестановок. Равным образом, вершины этого многогранника можно понимать как описание всех совершенных паросочетаний полного двудольного графа, а задачу линейной оптимизации на этом многограннике можно рассматривать как задачу поиска взвешенного минимального совершенного паросочетания. Теорема Биркгофа утверждает, что такой многогранник можно описать с помощью двух типов линейных неравенств. Во-первых, каждый элемент матрицы неотрицателен, во-вторых, для каждого столбца и для каждой строки сумма элементов матрицы равна единице. Ограничения на сумму по строкам и столбцам определяют линейное подпространство размерности n² − 2n + 1, в котором лежит многогранник Биркгофа, а ограничения на неотрицательность элементов матрицы задают грани многоранника в этом подпространстве.

Многогранник Биркгофа необычен в том, что известно полное описание его граней. Для множества других 0-1 многогранников существует экспоненциально (или суперэкспоненционально) много граней и только частичное их описание доступно.

См. также

• Абстракный многогранник
• Абстрактная коммутативная алгебра
• Симплициальная сфера

Литература

• Michel L. Balinski On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — 1961. — Т. 11. — С. 431–434. — DOI:10.2140/pjm.1961.11.431..
• Roswitha Blind, Peter Mani-Levitska Puzzles and polytope isomorphisms // Aequationes Mathematicae. — 1987. — Т. 34, вып. 2-3. — С. 287–297. — DOI:10.1007/BF01830678..
• William Cook, Paul D. Seymour. Polyhedral Combinatorics. — American Mathematical Society, 1989. — (DIMACS Series in Discrete Mathematics and Theoretical Computer Science). — ISBN 978-0-8218-6591-0..
• Eric J. Friedman Finding a simple polytope from its graph in polynomial time // Discrete and Computational Geometry. — 2009. — Т. 41, вып. 2. — С. 249–256. — DOI:10.1007/s00454-008-9121-7..
• Christoph Haase, Stefan Kiefer The Complexity of the Kth Largest Subset Problem and Related Problems. — 2015.
• A census of flag-vectors of 4-polytopes. — 2000.. В Kalai, Ziegler 2000, стр. 105—110.
• Gil Kalai A simple way to tell a simple polytope from its graph // Journal of Combinatorial Theory. — 1988. — Т. 49, вып. 2. — С. 381–383. — DOI:10.1016/0097-3165(88)90064-7..
• Gil Kalai, Daniel Kleitman A quasi-polynomial bound for the diameter of graphs of polyhedra // Bulletin of the American Mathematical Society. — 1992. — Т. 26, вып. 2. — С. 315–316. — DOI:10.1090/S0273-0979-1992-00285-9. — arXiv:math/9204233..
• , ISBN 978-3-7643-6351-2 .
• Peter McMullen The maximum numbers of faces of a convex polytope // Mathematika. — 1970. — Т. 17. — С. 179–184. — DOI:10.1112/S0025579300002850..
• Denis Naddef The Hirsch conjecture is true for (0,1)-polytopes // Mathematical Programming. — 1989. — Т. 45, вып. 1. — С. 109–110. — DOI:10.1007/BF01589099..
• Francisco Santos Leal A counterexample to the Hirsch conjecture // Annals of Mathematics. — Princeton University and Institute for Advanced Study, 2011. — Т. 176, вып. 1. — С. 383–412. — DOI:10.4007/annals.2012.176.1.7. — arXiv:1006.2814.
• Alexander Schrijver. Polyhedral Combinatorics. — Centrum voor Wiskunde en Informatica, 1987..
• Ernst Steinitz. Über die Eulerschen Polyederrelationen. — Archiv für Mathematik und Physik. — 1906. — Т. 11. — С. 86–88..
• Günter M. Ziegler. Lectures on Polytopes. — Springer-Verlag, 1995. — Т. 152. — (Graduate Texts in Mathematics). — ISBN 0-387-94365-X..
• Günter M. Ziegler Lectures on 0-1 polytopes. — 2000.. В Kalai, Ziegler 2000.

Ссылки

• Gil Kalai Five Open Problems Regarding Convex Polytopes. — 2008..

Отрывок, характеризующий Комбинаторика многогранников

Первые войска двинулись в ночь. Войска, шедшие ночью, не торопились и двигались медленно и степенно; но на рассвете двигавшиеся войска, подходя к Дорогомиловскому мосту, увидали впереди себя, на другой стороне, теснящиеся, спешащие по мосту и на той стороне поднимающиеся и запружающие улицы и переулки, и позади себя – напирающие, бесконечные массы войск. И беспричинная поспешность и тревога овладели войсками. Все бросилось вперед к мосту, на мост, в броды и в лодки. Кутузов велел обвезти себя задними улицами на ту сторону Москвы.
К десяти часам утра 2 го сентября в Дорогомиловском предместье оставались на просторе одни войска ариергарда. Армия была уже на той стороне Москвы и за Москвою.
В это же время, в десять часов утра 2 го сентября, Наполеон стоял между своими войсками на Поклонной горе и смотрел на открывавшееся перед ним зрелище. Начиная с 26 го августа и по 2 е сентября, от Бородинского сражения и до вступления неприятеля в Москву, во все дни этой тревожной, этой памятной недели стояла та необычайная, всегда удивляющая людей осенняя погода, когда низкое солнце греет жарче, чем весной, когда все блестит в редком, чистом воздухе так, что глаза режет, когда грудь крепнет и свежеет, вдыхая осенний пахучий воздух, когда ночи даже бывают теплые и когда в темных теплых ночах этих с неба беспрестанно, пугая и радуя, сыплются золотые звезды.
2 го сентября в десять часов утра была такая погода. Блеск утра был волшебный. Москва с Поклонной горы расстилалась просторно с своей рекой, своими садами и церквами и, казалось, жила своей жизнью, трепеща, как звезды, своими куполами в лучах солнца.
При виде странного города с невиданными формами необыкновенной архитектуры Наполеон испытывал то несколько завистливое и беспокойное любопытство, которое испытывают люди при виде форм не знающей о них, чуждой жизни. Очевидно, город этот жил всеми силами своей жизни. По тем неопределимым признакам, по которым на дальнем расстоянии безошибочно узнается живое тело от мертвого. Наполеон с Поклонной горы видел трепетание жизни в городе и чувствовал как бы дыханио этого большого и красивого тела.
– Cette ville asiatique aux innombrables eglises, Moscou la sainte. La voila donc enfin, cette fameuse ville! Il etait temps, [Этот азиатский город с бесчисленными церквами, Москва, святая их Москва! Вот он, наконец, этот знаменитый город! Пора!] – сказал Наполеон и, слезши с лошади, велел разложить перед собою план этой Moscou и подозвал переводчика Lelorgne d'Ideville. «Une ville occupee par l'ennemi ressemble a une fille qui a perdu son honneur, [Город, занятый неприятелем, подобен девушке, потерявшей невинность.] – думал он (как он и говорил это Тучкову в Смоленске). И с этой точки зрения он смотрел на лежавшую перед ним, невиданную еще им восточную красавицу. Ему странно было самому, что, наконец, свершилось его давнишнее, казавшееся ему невозможным, желание. В ясном утреннем свете он смотрел то на город, то на план, проверяя подробности этого города, и уверенность обладания волновала и ужасала его.
«Но разве могло быть иначе? – подумал он. – Вот она, эта столица, у моих ног, ожидая судьбы своей. Где теперь Александр и что думает он? Странный, красивый, величественный город! И странная и величественная эта минута! В каком свете представляюсь я им! – думал он о своих войсках. – Вот она, награда для всех этих маловерных, – думал он, оглядываясь на приближенных и на подходившие и строившиеся войска. – Одно мое слово, одно движение моей руки, и погибла эта древняя столица des Czars. Mais ma clemence est toujours prompte a descendre sur les vaincus. [царей. Но мое милосердие всегда готово низойти к побежденным.] Я должен быть великодушен и истинно велик. Но нет, это не правда, что я в Москве, – вдруг приходило ему в голову. – Однако вот она лежит у моих ног, играя и дрожа золотыми куполами и крестами в лучах солнца. Но я пощажу ее. На древних памятниках варварства и деспотизма я напишу великие слова справедливости и милосердия… Александр больнее всего поймет именно это, я знаю его. (Наполеону казалось, что главное значение того, что совершалось, заключалось в личной борьбе его с Александром.) С высот Кремля, – да, это Кремль, да, – я дам им законы справедливости, я покажу им значение истинной цивилизации, я заставлю поколения бояр с любовью поминать имя своего завоевателя. Я скажу депутации, что я не хотел и не хочу войны; что я вел войну только с ложной политикой их двора, что я люблю и уважаю Александра и что приму условия мира в Москве, достойные меня и моих народов. Я не хочу воспользоваться счастьем войны для унижения уважаемого государя. Бояре – скажу я им: я не хочу войны, а хочу мира и благоденствия всех моих подданных. Впрочем, я знаю, что присутствие их воодушевит меня, и я скажу им, как я всегда говорю: ясно, торжественно и велико. Но неужели это правда, что я в Москве? Да, вот она!»
– Qu'on m'amene les boyards, [Приведите бояр.] – обратился он к свите. Генерал с блестящей свитой тотчас же поскакал за боярами.
Прошло два часа. Наполеон позавтракал и опять стоял на том же месте на Поклонной горе, ожидая депутацию. Речь его к боярам уже ясно сложилась в его воображении. Речь эта была исполнена достоинства и того величия, которое понимал Наполеон.
Тот тон великодушия, в котором намерен был действовать в Москве Наполеон, увлек его самого. Он в воображении своем назначал дни reunion dans le palais des Czars [собраний во дворце царей.], где должны были сходиться русские вельможи с вельможами французского императора. Он назначал мысленно губернатора, такого, который бы сумел привлечь к себе население. Узнав о том, что в Москве много богоугодных заведений, он в воображении своем решал, что все эти заведения будут осыпаны его милостями. Он думал, что как в Африке надо было сидеть в бурнусе в мечети, так в Москве надо было быть милостивым, как цари. И, чтобы окончательно тронуть сердца русских, он, как и каждый француз, не могущий себе вообразить ничего чувствительного без упоминания о ma chere, ma tendre, ma pauvre mere, [моей милой, нежной, бедной матери ,] он решил, что на всех этих заведениях он велит написать большими буквами: Etablissement dedie a ma chere Mere. Нет, просто: Maison de ma Mere, [Учреждение, посвященное моей милой матери… Дом моей матери.] – решил он сам с собою. «Но неужели я в Москве? Да, вот она передо мной. Но что же так долго не является депутация города?» – думал он.
Между тем в задах свиты императора происходило шепотом взволнованное совещание между его генералами и маршалами. Посланные за депутацией вернулись с известием, что Москва пуста, что все уехали и ушли из нее. Лица совещавшихся были бледны и взволнованны. Не то, что Москва была оставлена жителями (как ни важно казалось это событие), пугало их, но их пугало то, каким образом объявить о том императору, каким образом, не ставя его величество в то страшное, называемое французами ridicule [смешным] положение, объявить ему, что он напрасно ждал бояр так долго, что есть толпы пьяных, но никого больше. Одни говорили, что надо было во что бы то ни стало собрать хоть какую нибудь депутацию, другие оспаривали это мнение и утверждали, что надо, осторожно и умно приготовив императора, объявить ему правду.
– Il faudra le lui dire tout de meme… – говорили господа свиты. – Mais, messieurs… [Однако же надо сказать ему… Но, господа…] – Положение было тем тяжеле, что император, обдумывая свои планы великодушия, терпеливо ходил взад и вперед перед планом, посматривая изредка из под руки по дороге в Москву и весело и гордо улыбаясь.
– Mais c'est impossible… [Но неловко… Невозможно…] – пожимая плечами, говорили господа свиты, не решаясь выговорить подразумеваемое страшное слово: le ridicule…
Между тем император, уставши от тщетного ожидания и своим актерским чутьем чувствуя, что величественная минута, продолжаясь слишком долго, начинает терять свою величественность, подал рукою знак. Раздался одинокий выстрел сигнальной пушки, и войска, с разных сторон обложившие Москву, двинулись в Москву, в Тверскую, Калужскую и Дорогомиловскую заставы. Быстрее и быстрее, перегоняя одни других, беглым шагом и рысью, двигались войска, скрываясь в поднимаемых ими облаках пыли и оглашая воздух сливающимися гулами криков.
Увлеченный движением войск, Наполеон доехал с войсками до Дорогомиловской заставы, но там опять остановился и, слезши с лошади, долго ходил у Камер коллежского вала, ожидая депутации.


Москва между тем была пуста. В ней были еще люди, в ней оставалась еще пятидесятая часть всех бывших прежде жителей, но она была пуста. Она была пуста, как пуст бывает домирающий обезматочивший улей.
В обезматочившем улье уже нет жизни, но на поверхностный взгляд он кажется таким же живым, как и другие.
Так же весело в жарких лучах полуденного солнца вьются пчелы вокруг обезматочившего улья, как и вокруг других живых ульев; так же издалека пахнет от него медом, так же влетают и вылетают из него пчелы. Но стоит приглядеться к нему, чтобы понять, что в улье этом уже нет жизни. Не так, как в живых ульях, летают пчелы, не тот запах, не тот звук поражают пчеловода. На стук пчеловода в стенку больного улья вместо прежнего, мгновенного, дружного ответа, шипенья десятков тысяч пчел, грозно поджимающих зад и быстрым боем крыльев производящих этот воздушный жизненный звук, – ему отвечают разрозненные жужжания, гулко раздающиеся в разных местах пустого улья. Из летка не пахнет, как прежде, спиртовым, душистым запахом меда и яда, не несет оттуда теплом полноты, а с запахом меда сливается запах пустоты и гнили. У летка нет больше готовящихся на погибель для защиты, поднявших кверху зады, трубящих тревогу стражей. Нет больше того ровного и тихого звука, трепетанья труда, подобного звуку кипенья, а слышится нескладный, разрозненный шум беспорядка. В улей и из улья робко и увертливо влетают и вылетают черные продолговатые, смазанные медом пчелы грабительницы; они не жалят, а ускользают от опасности. Прежде только с ношами влетали, а вылетали пустые пчелы, теперь вылетают с ношами. Пчеловод открывает нижнюю колодезню и вглядывается в нижнюю часть улья. Вместо прежде висевших до уза (нижнего дна) черных, усмиренных трудом плетей сочных пчел, держащих за ноги друг друга и с непрерывным шепотом труда тянущих вощину, – сонные, ссохшиеся пчелы в разные стороны бредут рассеянно по дну и стенкам улья. Вместо чисто залепленного клеем и сметенного веерами крыльев пола на дне лежат крошки вощин, испражнения пчел, полумертвые, чуть шевелящие ножками и совершенно мертвые, неприбранные пчелы.
Пчеловод открывает верхнюю колодезню и осматривает голову улья. Вместо сплошных рядов пчел, облепивших все промежутки сотов и греющих детву, он видит искусную, сложную работу сотов, но уже не в том виде девственности, в котором она бывала прежде. Все запущено и загажено. Грабительницы – черные пчелы – шныряют быстро и украдисто по работам; свои пчелы, ссохшиеся, короткие, вялые, как будто старые, медленно бродят, никому не мешая, ничего не желая и потеряв сознание жизни. Трутни, шершни, шмели, бабочки бестолково стучатся на лету о стенки улья. Кое где между вощинами с мертвыми детьми и медом изредка слышится с разных сторон сердитое брюзжание; где нибудь две пчелы, по старой привычке и памяти очищая гнездо улья, старательно, сверх сил, тащат прочь мертвую пчелу или шмеля, сами не зная, для чего они это делают. В другом углу другие две старые пчелы лениво дерутся, или чистятся, или кормят одна другую, сами не зная, враждебно или дружелюбно они это делают. В третьем месте толпа пчел, давя друг друга, нападает на какую нибудь жертву и бьет и душит ее. И ослабевшая или убитая пчела медленно, легко, как пух, спадает сверху в кучу трупов. Пчеловод разворачивает две средние вощины, чтобы видеть гнездо. Вместо прежних сплошных черных кругов спинка с спинкой сидящих тысяч пчел и блюдущих высшие тайны родного дела, он видит сотни унылых, полуживых и заснувших остовов пчел. Они почти все умерли, сами не зная этого, сидя на святыне, которую они блюли и которой уже нет больше. От них пахнет гнилью и смертью. Только некоторые из них шевелятся, поднимаются, вяло летят и садятся на руку врагу, не в силах умереть, жаля его, – остальные, мертвые, как рыбья чешуя, легко сыплются вниз. Пчеловод закрывает колодезню, отмечает мелом колодку и, выбрав время, выламывает и выжигает ее.
Так пуста была Москва, когда Наполеон, усталый, беспокойный и нахмуренный, ходил взад и вперед у Камерколлежского вала, ожидая того хотя внешнего, но необходимого, по его понятиям, соблюдения приличий, – депутации.
В разных углах Москвы только бессмысленно еще шевелились люди, соблюдая старые привычки и не понимая того, что они делали.
Когда Наполеону с должной осторожностью было объявлено, что Москва пуста, он сердито взглянул на доносившего об этом и, отвернувшись, продолжал ходить молча.