Граф (математика)

Граф (англ. graph) — основной объект изучения математической теории графов, совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа, в котором вершины — это статьи, а дуги (ориентированные рёбра) — гиперссылки (тематическая карта).

Определения

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

Граф

Граф, или неориентированный граф <math>G</math> — это упорядоченная пара <math>G := (V, E)</math>, где <math>V</math> — это непустое множество вершин или узлов, а <math>E</math> — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

<math>V</math> (а значит и, <math>E</math>, иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов, поскольку не все утверждения, имеющие место для конечных совокупностей, выполняются в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе <math>|V|</math> — порядком, число рёбер <math>|E|</math> — размером графа.

Вершины <math>u</math> и <math>v</math> называются концевыми вершинами (или просто концами) ребра <math>e=\{u,v\}</math>. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть <math>e=\{v,v\}</math>.

Степенью <math>\deg V</math> вершины <math>V</math> называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф

Ориентированный граф (сокращённо орграф) <math>G</math> — это упорядоченная пара <math>G := (V, A)</math>, где <math>V</math> — непустое множество вершин или узлов, и <math>A</math> — множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин <math>(v, w)</math>, где вершину <math>v</math> называют началом, а <math>w</math> — концом дуги. Можно сказать, что дуга <math>v \to w</math> ведёт от вершины <math>v</math> к вершине <math>w</math>.

Смешанный граф

Смешанный граф <math>G</math> — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой <math>G := (V, E, A)</math>, где <math>V</math>, <math>E</math> и <math>A</math> определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

Изоморфные графы

Граф <math>G</math> называется изоморфным графу <math>H</math>, если существует биекция <math>f</math> из множества вершин графа <math>G</math> в множество вершин графа <math>H</math>, обладающая следующим свойством: если в графе <math>G</math> есть ребро из вершины <math>A</math> в вершину <math>B</math>, то в графе <math>H</math> должно быть ребро из вершины <math>f(A)</math> в вершину <math>f(B)</math> и наоборот — если в графе <math>H</math> есть ребро из вершины <math>A</math> в вершину <math>B</math>, то в графе <math>G</math> должно быть ребро из вершины <math>f^{-1}(A)</math> в вершину <math>f^{-1}(B)</math>. В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

Прочие связанные определения

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

Ориентированным маршрутом (или путём) в орграфе называют конечную последовательность вершин и дуг, в которой каждый элемент инцидентен предыдущему и последующему.

Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины <math>u</math> и <math>v</math> являются концами некоторого ребра, то согласно данному определению, последовательность <math>(u,v,u)</math> является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

Простейшие свойства путей и циклов:

• всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины;
• всякий простой неэлементарный путь содержит элементарный цикл;
• всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро);
• петля — элементарный цикл.

Бинарное отношение на множестве вершин графа, заданное как «существует путь из <math>u</math> в <math>v</math>», является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Всякий максимальный связный подграф графа <math>G</math> называется связной компонентой (или просто компонентой) графа <math>G</math>. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов.

Ребро графа называется мостом, если его удаление увеличивает число компонент.

Дополнительные характеристики графов

Граф называется:

• связным, если для любых вершин <math>u</math>,<math>v</math> есть путь из <math>u</math> в <math>v</math>.
• сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.
• деревом, если он связный и не содержит нетривиальных циклов.
• полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
• двудольным, если его вершины можно разбить на два непересекающихся подмножества <math>V_1</math> и <math>V_2</math> так, что всякое ребро соединяет вершину из <math>V_1</math> с вершиной из <math>V_2</math>.
• k-дольным, если его вершины можно разбить на <math>k</math> непересекающихся подмножества <math>V_1</math>, <math>V_2</math>, …, <math>V_k</math> так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
• полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
• планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
• взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.
• хордальным, если граф не содержит индуцированных циклов с длиной больше трёх.

Также бывает:

• k-раскрашиваемым
• k-хроматическим

Обобщение понятия графа

Простой граф является одномерным симплициальным комплексом.

Более абстрактно, граф можно задать как тройку <math>(V, E, \varphi)</math>, где <math>V</math> и <math>E</math> — некоторые множества (вершин и рёбер, соотв.), а <math>\varphi</math> — функция инцидентности (или инцидентор), сопоставляющая каждому ребру <math>e\in E</math> (упорядоченную или неупорядоченную) пару вершин <math>u</math> и <math>v</math> из <math>V</math> (его концов). Частными случаями этого понятия являются:

• ориентированные графы (орграфы) — когда <math>\varphi(e)</math> всегда является упорядоченной парой вершин;
• неориентированные графы — когда <math>\varphi(e)</math> всегда является неупорядоченной парой вершин;
• смешанные графы — граф, в котором встречаются как ориентированные, так и неориентированные рёбра и петли;
• эйлеровы графы — граф, в котором существует циклический эйлеров путь (эйлеров цикл);
• мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
• псевдографы — это мультиграфы, допускающие наличие петель;
• простые графы — не имеющие петель и кратных рёбер.

Под данное выше определение не подходят некоторые другие обобщения:

• гиперграф — если ребро может соединять более двух вершин.
• ультраграф — если между элементами <math>x_i</math> и <math>u_j</math> существуют бинарные отношения инцидентности.

Способы представления графа в информатике

Матрица смежности

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

Это наиболее удобный способ представления плотных графов.

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.

• Двумерный массив;
• Матрица с пропусками;
• Неявное задание (при помощи функции).

Матрица инцидентности

Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа. В ячейку матрицы на пересечении строки <math>i</math> со столбцом <math>j</math> записывается:

1

в случае, если связь <math>j</math> «выходит» из вершины <math>i</math>,

−1,

если связь «входит» в вершину,

0

во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким (размер пропорционален <math>|V| |E|</math>) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).

Список смежности

Список, где каждой вершине графа соответствует строка, в которой хранится список смежных вершин. Такая структура данных не является таблицей в обычном понимании, а представляет собой «список списков».

Размер занимаемой памяти: <math>O(|V|+|E|)</math>.

Это наиболее удобный способ для представления разреженных графов, а также при реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.

Список рёбер

Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру.

Размер занимаемой памяти: <math>O(|E|)</math>.

Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.

Языки описания и программы построения графов

Языки описания

Для описания графов в целях, пригодных для машинной обработки и одновременно удобном для человеческого восприятия, используется несколько стандартизированных языков, среди которых:

• DOT
• GraphML
• Trivial Graph Format
• GML
• GXL
• XGMML
• DGML

Программы для построения

Разработана серия коммерческих программ для построения графов, так, построение графов лежит в основе прикладных программных пакетов фирмы ILOG (с 2009 года принадлежит корпорации IBM), среди других программ — GoView, Lassalle AddFlow, LEDA (есть бесплатная редакция).

Также существует свободная программа для построения графов igraph и свободная библиотека Boost.

Программы для визуализации

Для визуализации графов применяются следующие программные средства:

• Graphviz (Eclipse Public License)
• LION Graph Visualizer.
• Графоанализатор — русскоязычная программа, с простым пользовательским интерфейсом (GNU LGPL; только для Windows).
• Gephi — графическая оболочка для представления и изучения графов (GNU GPL, CDDL).
• Библиотека GraphX — свободная библиотека для .NET для расчёта и отрисовки графов, использует WPF 4.0.
• Библиотека MSAGL — свободная библиотека для .NET.

См. также

• Прямое произведение графов
• Объектный граф

Литература

• Оре О. Теория графов. — М.: Наука, 1968. — 336 с.
• Уилсон Р. Введение в теорию графов. — М.: Мир, 1977. — 208 с.
• Харари Ф. Теория графов. — М.: Мир, 1973.
• Кормен Т. М. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
• Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9.
• Касьянов В. Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — С. 1104. — ISBN 5-94157-184-4.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
• Кирсанов М. Н. Графы в Maple. — М.: Физматлит, 2007. — 168 с.
• Графы // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 86-88. — 352 с.

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

Русские войска, отступив от Бородина, стояли у Филей. Ермолов, ездивший для осмотра позиции, подъехал к фельдмаршалу.
– Драться на этой позиции нет возможности, – сказал он. Кутузов удивленно посмотрел на него и заставил его повторить сказанные слова. Когда он проговорил, Кутузов протянул ему руку.
– Дай ка руку, – сказал он, и, повернув ее так, чтобы ощупать его пульс, он сказал: – Ты нездоров, голубчик. Подумай, что ты говоришь.
Кутузов на Поклонной горе, в шести верстах от Дорогомиловской заставы, вышел из экипажа и сел на лавку на краю дороги. Огромная толпа генералов собралась вокруг него. Граф Растопчин, приехав из Москвы, присоединился к ним. Все это блестящее общество, разбившись на несколько кружков, говорило между собой о выгодах и невыгодах позиции, о положении войск, о предполагаемых планах, о состоянии Москвы, вообще о вопросах военных. Все чувствовали, что хотя и не были призваны на то, что хотя это не было так названо, но что это был военный совет. Разговоры все держались в области общих вопросов. Ежели кто и сообщал или узнавал личные новости, то про это говорилось шепотом, и тотчас переходили опять к общим вопросам: ни шуток, ни смеха, ни улыбок даже не было заметно между всеми этими людьми. Все, очевидно, с усилием, старались держаться на высота положения. И все группы, разговаривая между собой, старались держаться в близости главнокомандующего (лавка которого составляла центр в этих кружках) и говорили так, чтобы он мог их слышать. Главнокомандующий слушал и иногда переспрашивал то, что говорили вокруг него, но сам не вступал в разговор и не выражал никакого мнения. Большей частью, послушав разговор какого нибудь кружка, он с видом разочарования, – как будто совсем не о том они говорили, что он желал знать, – отворачивался. Одни говорили о выбранной позиции, критикуя не столько самую позицию, сколько умственные способности тех, которые ее выбрали; другие доказывали, что ошибка была сделана прежде, что надо было принять сраженье еще третьего дня; третьи говорили о битве при Саламанке, про которую рассказывал только что приехавший француз Кросар в испанском мундире. (Француз этот вместе с одним из немецких принцев, служивших в русской армии, разбирал осаду Сарагоссы, предвидя возможность так же защищать Москву.) В четвертом кружке граф Растопчин говорил о том, что он с московской дружиной готов погибнуть под стенами столицы, но что все таки он не может не сожалеть о той неизвестности, в которой он был оставлен, и что, ежели бы он это знал прежде, было бы другое… Пятые, выказывая глубину своих стратегических соображений, говорили о том направлении, которое должны будут принять войска. Шестые говорили совершенную бессмыслицу. Лицо Кутузова становилось все озабоченнее и печальнее. Из всех разговоров этих Кутузов видел одно: защищать Москву не было никакой физической возможности в полном значении этих слов, то есть до такой степени не было возможности, что ежели бы какой нибудь безумный главнокомандующий отдал приказ о даче сражения, то произошла бы путаница и сражения все таки бы не было; не было бы потому, что все высшие начальники не только признавали эту позицию невозможной, но в разговорах своих обсуждали только то, что произойдет после несомненного оставления этой позиции. Как же могли начальники вести свои войска на поле сражения, которое они считали невозможным? Низшие начальники, даже солдаты (которые тоже рассуждают), также признавали позицию невозможной и потому не могли идти драться с уверенностью поражения. Ежели Бенигсен настаивал на защите этой позиции и другие еще обсуждали ее, то вопрос этот уже не имел значения сам по себе, а имел значение только как предлог для спора и интриги. Это понимал Кутузов.
Бенигсен, выбрав позицию, горячо выставляя свой русский патриотизм (которого не мог, не морщась, выслушивать Кутузов), настаивал на защите Москвы. Кутузов ясно как день видел цель Бенигсена: в случае неудачи защиты – свалить вину на Кутузова, доведшего войска без сражения до Воробьевых гор, а в случае успеха – себе приписать его; в случае же отказа – очистить себя в преступлении оставления Москвы. Но этот вопрос интриги не занимал теперь старого человека. Один страшный вопрос занимал его. И на вопрос этот он ни от кого не слышал ответа. Вопрос состоял для него теперь только в том: «Неужели это я допустил до Москвы Наполеона, и когда же я это сделал? Когда это решилось? Неужели вчера, когда я послал к Платову приказ отступить, или третьего дня вечером, когда я задремал и приказал Бенигсену распорядиться? Или еще прежде?.. но когда, когда же решилось это страшное дело? Москва должна быть оставлена. Войска должны отступить, и надо отдать это приказание». Отдать это страшное приказание казалось ему одно и то же, что отказаться от командования армией. А мало того, что он любил власть, привык к ней (почет, отдаваемый князю Прозоровскому, при котором он состоял в Турции, дразнил его), он был убежден, что ему было предназначено спасение России и что потому только, против воли государя и по воле народа, он был избрал главнокомандующим. Он был убежден, что он один и этих трудных условиях мог держаться во главе армии, что он один во всем мире был в состоянии без ужаса знать своим противником непобедимого Наполеона; и он ужасался мысли о том приказании, которое он должен был отдать. Но надо было решить что нибудь, надо было прекратить эти разговоры вокруг него, которые начинали принимать слишком свободный характер.
Он подозвал к себе старших генералов.
– Ma tete fut elle bonne ou mauvaise, n'a qu'a s'aider d'elle meme, [Хороша ли, плоха ли моя голова, а положиться больше не на кого,] – сказал он, вставая с лавки, и поехал в Фили, где стояли его экипажи.


В просторной, лучшей избе мужика Андрея Савостьянова в два часа собрался совет. Мужики, бабы и дети мужицкой большой семьи теснились в черной избе через сени. Одна только внучка Андрея, Малаша, шестилетняя девочка, которой светлейший, приласкав ее, дал за чаем кусок сахара, оставалась на печи в большой избе. Малаша робко и радостно смотрела с печи на лица, мундиры и кресты генералов, одного за другим входивших в избу и рассаживавшихся в красном углу, на широких лавках под образами. Сам дедушка, как внутренне называла Maлаша Кутузова, сидел от них особо, в темном углу за печкой. Он сидел, глубоко опустившись в складное кресло, и беспрестанно покряхтывал и расправлял воротник сюртука, который, хотя и расстегнутый, все как будто жал его шею. Входившие один за другим подходили к фельдмаршалу; некоторым он пожимал руку, некоторым кивал головой. Адъютант Кайсаров хотел было отдернуть занавеску в окне против Кутузова, но Кутузов сердито замахал ему рукой, и Кайсаров понял, что светлейший не хочет, чтобы видели его лицо.
Вокруг мужицкого елового стола, на котором лежали карты, планы, карандаши, бумаги, собралось так много народа, что денщики принесли еще лавку и поставили у стола. На лавку эту сели пришедшие: Ермолов, Кайсаров и Толь. Под самыми образами, на первом месте, сидел с Георгием на шее, с бледным болезненным лицом и с своим высоким лбом, сливающимся с голой головой, Барклай де Толли. Второй уже день он мучился лихорадкой, и в это самое время его знобило и ломало. Рядом с ним сидел Уваров и негромким голосом (как и все говорили) что то, быстро делая жесты, сообщал Барклаю. Маленький, кругленький Дохтуров, приподняв брови и сложив руки на животе, внимательно прислушивался. С другой стороны сидел, облокотивши на руку свою широкую, с смелыми чертами и блестящими глазами голову, граф Остерман Толстой и казался погруженным в свои мысли. Раевский с выражением нетерпения, привычным жестом наперед курчавя свои черные волосы на висках, поглядывал то на Кутузова, то на входную дверь. Твердое, красивое и доброе лицо Коновницына светилось нежной и хитрой улыбкой. Он встретил взгляд Малаши и глазами делал ей знаки, которые заставляли девочку улыбаться.
Все ждали Бенигсена, который доканчивал свой вкусный обед под предлогом нового осмотра позиции. Его ждали от четырех до шести часов, и во все это время не приступали к совещанию и тихими голосами вели посторонние разговоры.
Только когда в избу вошел Бенигсен, Кутузов выдвинулся из своего угла и подвинулся к столу, но настолько, что лицо его не было освещено поданными на стол свечами.
Бенигсен открыл совет вопросом: «Оставить ли без боя священную и древнюю столицу России или защищать ее?» Последовало долгое и общее молчание. Все лица нахмурились, и в тишине слышалось сердитое кряхтенье и покашливанье Кутузова. Все глаза смотрели на него. Малаша тоже смотрела на дедушку. Она ближе всех была к нему и видела, как лицо его сморщилось: он точно собрался плакать. Но это продолжалось недолго.
– Священную древнюю столицу России! – вдруг заговорил он, сердитым голосом повторяя слова Бенигсена и этим указывая на фальшивую ноту этих слов. – Позвольте вам сказать, ваше сиятельство, что вопрос этот не имеет смысла для русского человека. (Он перевалился вперед своим тяжелым телом.) Такой вопрос нельзя ставить, и такой вопрос не имеет смысла. Вопрос, для которого я просил собраться этих господ, это вопрос военный. Вопрос следующий: «Спасенье России в армии. Выгоднее ли рисковать потерею армии и Москвы, приняв сраженье, или отдать Москву без сражения? Вот на какой вопрос я желаю знать ваше мнение». (Он откачнулся назад на спинку кресла.)
Начались прения. Бенигсен не считал еще игру проигранною. Допуская мнение Барклая и других о невозможности принять оборонительное сражение под Филями, он, проникнувшись русским патриотизмом и любовью к Москве, предлагал перевести войска в ночи с правого на левый фланг и ударить на другой день на правое крыло французов. Мнения разделились, были споры в пользу и против этого мнения. Ермолов, Дохтуров и Раевский согласились с мнением Бенигсена. Руководимые ли чувством потребности жертвы пред оставлением столицы или другими личными соображениями, но эти генералы как бы не понимали того, что настоящий совет не мог изменить неизбежного хода дел и что Москва уже теперь оставлена. Остальные генералы понимали это и, оставляя в стороне вопрос о Москве, говорили о том направлении, которое в своем отступлении должно было принять войско. Малаша, которая, не спуская глаз, смотрела на то, что делалось перед ней, иначе понимала значение этого совета. Ей казалось, что дело было только в личной борьбе между «дедушкой» и «длиннополым», как она называла Бенигсена. Она видела, что они злились, когда говорили друг с другом, и в душе своей она держала сторону дедушки. В средине разговора она заметила быстрый лукавый взгляд, брошенный дедушкой на Бенигсена, и вслед за тем, к радости своей, заметила, что дедушка, сказав что то длиннополому, осадил его: Бенигсен вдруг покраснел и сердито прошелся по избе. Слова, так подействовавшие на Бенигсена, были спокойным и тихим голосом выраженное Кутузовым мнение о выгоде и невыгоде предложения Бенигсена: о переводе в ночи войск с правого на левый фланг для атаки правого крыла французов.
– Я, господа, – сказал Кутузов, – не могу одобрить плана графа. Передвижения войск в близком расстоянии от неприятеля всегда бывают опасны, и военная история подтверждает это соображение. Так, например… (Кутузов как будто задумался, приискивая пример и светлым, наивным взглядом глядя на Бенигсена.) Да вот хоть бы Фридландское сражение, которое, как я думаю, граф хорошо помнит, было… не вполне удачно только оттого, что войска наши перестроивались в слишком близком расстоянии от неприятеля… – Последовало, показавшееся всем очень продолжительным, минутное молчание.
Прения опять возобновились, но часто наступали перерывы, и чувствовалось, что говорить больше не о чем.
Во время одного из таких перерывов Кутузов тяжело вздохнул, как бы сбираясь говорить. Все оглянулись на него.
– Eh bien, messieurs! Je vois que c'est moi qui payerai les pots casses, [Итак, господа, стало быть, мне платить за перебитые горшки,] – сказал он. И, медленно приподнявшись, он подошел к столу. – Господа, я слышал ваши мнения. Некоторые будут несогласны со мной. Но я (он остановился) властью, врученной мне моим государем и отечеством, я – приказываю отступление.
Вслед за этим генералы стали расходиться с той же торжественной и молчаливой осторожностью, с которой расходятся после похорон.
Некоторые из генералов негромким голосом, совсем в другом диапазоне, чем когда они говорили на совете, передали кое что главнокомандующему.
Малаша, которую уже давно ждали ужинать, осторожно спустилась задом с полатей, цепляясь босыми ножонками за уступы печки, и, замешавшись между ног генералов, шмыгнула в дверь.
Отпустив генералов, Кутузов долго сидел, облокотившись на стол, и думал все о том же страшном вопросе: «Когда же, когда же наконец решилось то, что оставлена Москва? Когда было сделано то, что решило вопрос, и кто виноват в этом?»
– Этого, этого я не ждал, – сказал он вошедшему к нему, уже поздно ночью, адъютанту Шнейдеру, – этого я не ждал! Этого я не думал!
– Вам надо отдохнуть, ваша светлость, – сказал Шнейдер.
– Да нет же! Будут же они лошадиное мясо жрать, как турки, – не отвечая, прокричал Кутузов, ударяя пухлым кулаком по столу, – будут и они, только бы…


В противоположность Кутузову, в то же время, в событии еще более важнейшем, чем отступление армии без боя, в оставлении Москвы и сожжении ее, Растопчин, представляющийся нам руководителем этого события, действовал совершенно иначе.
Событие это – оставление Москвы и сожжение ее – было так же неизбежно, как и отступление войск без боя за Москву после Бородинского сражения.