![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Все сказанное в этом параграфе о графах в равной степени относится к мультиграфам.
Начало теории графов как раздела математики связывают с так называемой задачей о кёнигсбергских мостах. Эта знаменитая в свое время задача состоит в следующем. Семь мостов города Кенигсберга (ныне Калининград) были расположены на реке Прегель так, как изображено
на рис. 43.1. Спрашивается, можно ли, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту?
Сопоставим плану города граф G, вершины которого соответствуют четырем разделяемым рекой участкам суши Л, В, С и D, а ребра — мостам. Этот граф (точнее, мультиграф) изображен на рис. 43.2. Таким образом, задачу о кёнигсбергских мостах можно на языке теории графов сформулировать так: есть ли в мультиграфе G цикл, содержащий все ребра этого мультиграфа?
Эйлер доказал неразрешимость задачи о кёнигсбергских мостах. В своей работе, опубликованной в 1736 году, он сформулировал и решил следующую общую проблему
рис 43.3 рис.43.4
теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?
Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом. Такой граф мож-но нарисовать, не отрывая карандаша от бумаги и не повторяя линий.
Например, граф, изображенный на рис. 43.3, является эйлеровым, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 4, 2, 6, 1). В этом графе есть и другие эйлеровы циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода ребер.
Помимо задачи о кёнигсбергских мостах известен ряд других старинных занимательных задач (головоломок), решение которых сводится к выяснению вопроса «является ли граф эйлеровым?». В одной из них требуется обрисовать фигуру, именуемую саблями (знаком) Магомета (рис. 43.4), не отрывая карандаша от бумаги и не повторяя линий.
Теорема 43.1 (Л. Эйлер, 1736 г.). Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.
Необходимость. Пусть G - эйлеров граф. Эйлеров цикл этого графа, проходя через каждую его верши-ну, входит в нее по одному ребру, а выходит по другому. Это означает, что каждая вершина инцидентна четному числу ребер эйлерова цикла, а поскольку такой цикл содержит все ребра графа G, то отсюда следует четность степеней всех его вершин.
Достаточность. Предположим теперь, что степени вершин графа G четны. Начнем цепь P1 из произвольной вершины v1 и будем продолжать ее, насколько возможно, выбирая каждый раз новое ребро. Так как степени всех вершин четны, то попав в очередную отличную от v1 вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро. Поэтому цепь P1 можно продолжить путем добавления этого ребра. Таким образом, построение цепи P1 закончится в вершине v1, т. е. P1 непременно будет циклом. Если окажется, что P1 содержит все ребра графа G, то это будет требуемый эйлеров цикл. В противном случае, удалив из G все ребра цикла P1, рассмотрим граф G1, полученный в результате такой операции. Поскольку P1 и G имели вершины только четных степеней, то, очевидно, и G1 будет обладать тем же свойством. Кроме того, в силу связности графа G графы P1 и G1 должны иметь хотя бы одну общую вершину v2. Теперь, начиная с вершины v2, построим цикл P2 в графе G1 подобно тому, как строили цикл P1. Обозначим через P’1 и P’’1 части цикла P1 от v1 до v2 и от v2 до v1 соответственно. Получим новый цикл
P1
который, начиная с V\, проходит по ребрам цепи Pi до V2, затем обходит все ребра цикла Рг и, наконец, возвращается в v\ по ребрам цепи Р[ (рис. 43.5).
Если цикл Рз не эйлеров, то проделав аналогичные построения, получим еще большой цикл и т. д. Этот процесс закончится построением эйлерова цикла. '<
Будем говорить, что набор ребер-но непересекающихся цепей (не обязательно простых) покрывает граф G, если каждое ребро графа G входит в одну из этих цепей. Пусть связный граф G содержит к вершин нечетной степени. По лемме о рукопожатиях к четно. Рассмотрим граф G', полученный добавлением к G новой вершины v и ребер, соединяющих v с вершинами графа G нечетной степени. Поскольку степени всех вершин графа G' четны, то G' содержит эйлеров цикл. Если теперь выбросить v из этого цикла, то получится к/2 цепей, содержащих все ребра графа G, т. е. покрывающих G.
С другой стороны, граф, являющийся объединением r ре-ерно-непересекающихся цепей, имеет самое большее 2r вершин нечетной степени. Поэтому меньшим числом це-пей граф G покрыть нельзя. Тем самым доказано
Следствие 43.2. Если связный граф содержит ров-но k вершин нечетной степени, то минимальное число покрывающих его реберно-непересекающихся цепей рано k/2.
В частности, когда к = 2, граф имеет цепь, которая соединяет вершины нечетной степени и содержит все ребра графа. Цепь, содержащую все ребра. графа, называют эйлеровой.
Из доказательства теоремы 43.1 видно, что эйлеров граф содержит, как правило, несколько эйлеровых циклов. Зная один такой цикл, получить новый можно сле-дующим простым приемом.
Пусть С — исходный эйлеров цикл, и вершина и проводится в этом цикле более одного раза. Рассмотрим часть (подцикл) цикла С, состоящую, из ребер и вершин, проходимых между k -м и l -м (к < l ) посещениями вершины v. Это будет некоторый цикл С\. Цикл С, как и всякий эйлеров цикл, задает некоторый порядок обхода ребер графа и индуцирует порядок прохождения ребер цикла С\. Если теперь порядок обхода ребер С\ изменить на обратный, а на остальных ребрах оставить его таким, каким он был в С, то, очевидно, получим новый эйлеров цикл С'. Например, в графе, изображенном на рис. 43.3, можно получить новый цикл С' = (1, 2, 6, 5, 4, 3, 2, 4, 6,1), полагая C=(1,2,3,4,5,6,2,4,6,1) и С\ = (2, 3, 4, 5, 6, 2).
В этом примере цикл С\ составлен из ребер, проходимых С между первым и вторым посещениями вершины 2.
Итак, изменив указанным способом эйлеров цикл, получаем новый эйлеров цикл. Следующая теорема, приводимая здесь без доказательства, утверждает, что последовательности таких изменений достаточно для получения всехэйлеровых циклов из данного.
Теорема 43.3 (А. Коциг, 1980 г.). Если С и С' —Элеровы циклы графа G, то в G существует такая последователъностъ эйлеровых циклов С = С\, Сг,..., Ск=С', что Ci+i получается из С г путем изменения порядка обxoдa ребер некоторого подцикла на обратный.
Естественно возникает вопрос: как найти хотя бы одинэйлеров цикл в эйлеровом графе G, т. е. как зану-меровать ребра графа числами 1, 2,...,/ EG/ с тем, что бы номер, присвоенный ребру, указывал, каким по счету это ребро проходится в эйлеровом цикле? Оказывается, это можно сделать, если нумеровать ребра, придерживаясь следующих двух правил:
1. Начиная с произвольной вершины и, присваиваем произвольному ребру uv номер 1. Затем вычеркиваем ребро иv и переходим в вершину v.
2. Пусть w — вершина, в которую мы пришли в результате выполнения предыдущего шага, и k-- номер, присвоенный некоторому ребру на этом шаге. Выбираем любое ребро, инцидентное вершине w, причем мост выбираем только в том случае, когда нет других возможностей; присваиваем выбранному ребру номер k+1 и вычеркиваем его.
Этот процесс, называемый алгоритмом Флёри, заканчивается, когда все ребра графа вычеркнуты, т. е. занумерованы.
Дадим теперь обоснование алгоритма. Прежде всего
заметим, что поскольку степень каждой вершины графа
G четна, то алгоритм может закончить работу только в той вершине, с которой начал. Поэтому он строит некоторый цикл G, и надо только доказать, что этот цикл включает все ребра графа G. Предположим, что это не так, и пусть G' — связная компонента графа G — EC, не являющаяся изолированной вершиной. Рассмотрим множество А ребер цикла С, инцидентных вершинам, вошедшим в G'. Ясно, что А=0. Пусть а -ребро из А, получившее в процессе работы алгоритма наибольший номер, т. е. вычеркнутое последним среди ребер А. Тогда, как легко видеть, ребро а к моменту вычеркивания было мостом в графе. Однако это противоречит правилу выбора очередного ребра.
Заметим, что эйлеровы графы достаточно редки. Верна следующая
Теорема 43.4 (Р. Рейд, 1962 г.). Почти нет эйлеровых графов.
Пусть ^i (/г) —множество всех эйлеровых графов из &(п) (см. § 12), а ^2 (и) — множество всех графов из &(п), степени всех вершин которых четны. Согласно теореме 43.1 имеем
(1)
Очевидно, что все графы из F2(п) можно получить, добавляя к некоторому графу из F(п— 1) новую вершину и соединяя ее со всеми вершинами нечетной степени.
Большая масса доказанных здесь теорем утверждает, что при выполнении определенных условий граф содержит гамильтонов цикл, причем метод доказательства таких теорем обычно дает и эффективный алгоритм построения са-мого гамильтонова цикла. В этом параграфе мы рассмот-рим несколько теорем такого рода (достаточных условий
гамильтоновости).
Интуитивно ясно, что если граф содержит много ребер и эти ребра к тому же достаточно равномерно распре делены, то граф «предрасположен» быть гамильтоновым. В трех приводимых ниже теоремах можно усмотреть
подтверждение этому.
Напомним, что степенной последовательностью графа называется список степеней его вершин.
Теорема 44.2 (В. Хватал, 1972 г.). Граф со степенной последовательностью d1 ≤ d2 ≤....≤ dn является гамилътоновым, если для всякого к, удовлетворяющего не равенствам 1≤к<п/2, истинна импликация
Теорему докажем от противного. Пусть существует негамильтонов граф, последовательность степеней вершин которого удовлетворяет условиям теоремы. Соединив две несмежные вершины такого графа ребром, получим, как легко видеть, граф со степенной последовательностью, снова удовлетворяющей условиям теоремы. Так как пол ный граф гамильтонов, то отсюда следует, что существу ет максимальный негамильтонов граф, степенная после довательность которого обладает таким же свойством. Этот граф будем обозначать через G. Таким образом, до бавление любого нового ребра к графу G приводит к по явлению в нем гамильтонова цикла. Поэтому любые две его несмежные вершины соединены гамильтоновой цепью. Выберем в графе G пару несмежных вершин v1 и vn так, чтобы величина deg v1 + deg vn была максимальной. Пусть v1 ,v2,..., vn — гамильтонова цепь, соединяющая
эти вершины.
Если в графе G вершины v1 и vj смежны, то вершина vn не может быть смежной с vj-1, поскольку в противном случае граф G содержал бы гамильтонов цикл
(v1,v2,..., vj-1,vn, vn-1,vn-2 ,..., vj+1,vj+1,v1)
(рис. 44.4). Таким образом, вершина vn не смежна по крайней мере с deg v1 вершинами, и поэтому deg vn ≤ п — 1 — deg v1. Отсюда получаем
deg v1 + deg vn ≤ n — 1< п.
![]() |
отмечалось, не менее чем deg v1. Поэтому выбрав k = deg v1 , получим dh≤ k< п/2. Следовательно, по условию теоремы dn-h ≥ п — k. Последнее означает, что имеется по крайней мере k + 1 вершин степени не меньше чем п — k. Такими вершинами являются, например, вершины со степенями dn,dn-1 ,...., dn-k. Поскольку deg v1 = k, то v1 не может быть смежной со всеми этими вершинами, и, значит, найдется такая вершина v1 не смежная с v1, что deg v1 ≥ ≥ п — k. Но тогда
deg v1 + deg v1t ≥ k + (n — k)> deg v1 + deg vn,
что противоречит выбору вершин v1 и vn. С помощью только что доказанной теоремы можно получить ряд других достаточных условий гамильтоновости. Эти условия проще и, естественно, слабее теоремы 44.2.
Теорема 44.3 (О. Оре, 1960 г.). Если для любой пары и и v несмежных вершин графа G порядка п≥3 выполняется неравенство deg и + deg v ≥ n, то G — га милътонов граф. > Пусть
VG = {v1 , v2 ,..., vn }, di = deg vi , i =1, n,
и d1 ≤ d2 ≤...≤ dn — степенная последовательность гра фа G. Согласно теореме 44.2 достаточно показать, что ус ловие нашей теоремы обеспечивает выполнение нера венств
dh>k, k =.l ,[n/ 2-1].
Доказательство проведем от противного. Пусть для не которого t € {1,..., [n/2— 1]} выполняется неравенство
dt < t. Существование индексов i и j таких, что i, j < t и vivj¢EG, привело бы к неравенствам
di + di<2dt <2t<n,
противоречащим условию теоремы. Следовательно, вер шины v1 ,v2 ,..., vt попарно смежны. Это вместе с неравенствами di < t (l=1, t) означает, что каждая вершина vi {1=1, t) смежна не более чем с одной вершиной vm, t + 1 < т < п. Далее, поскольку t < п/2, то п — t > t. По этому найдется вершина vi, t + 1 < j< п, не смежная ни с одной из вершин vi (i = l, t). Следовательно, deg vi < < n - t - 1. Но тогда для пары несмежных вершин vt и vj имеем неравенство deg vt + deg vj < n, которое противоречит условию теоремы.
Из этой теоремы непосредственно вытекает следующая Теорема 44.4 (Г. Дирак, 1952 г.). Если |G|=n>3 и для любой вершины v графа G выполняется неравенство deg v > n/2, то G — гамильтонов граф.
Нетрудно заметить, что во всяком n-вершинном графе, удовлетворяющем условиям любой из рассмотренных выше теорем 44.2—44.4, число ребер не меньше чем (п— 1)2/4. С другой стороны, n -вершинный планарный граф, как мы знаем, содержит не более З n — 6 ребер. Поэтому рассмотренные выше достаточные условия заведомо неприменимы к планарным графам.
Легко указать 2-связный негамильтонов планарный граф. Таким графом является, например, тэтаграф. Привести пример 3-связного планарного графа без гамильтонова цикла уже не столь просто. Такой граф, оказывается, должен содержать не менее 11 вершин. Этот факт был установлен Д. Барнеттом и Е. Юковичем (1970 г.). Найденный ими негамильтонов планарный 3-связный граф с минимальным числом вершин изображен на рис. 44.5. В том, что этот граф не содержит гамильтонова цикла, можно убедиться, проделав не слишком большой в данном случае перебор вариантов. Проще, однако, заметить, что он — двудольный и, следовательно, не содержит циклов нечетной длины, в частности, гамильтоновых циклов.
Следующая теорема — один из наиболее сильных результатов, касающихся гамильтоновых графов.
Теорема 44.5 (У. Татт, 1946 г.). Всякий 4-связный планарный граф является гамилътоновым.
Весьма сложное доказательство этой теоремы здесь опускается.
Следствие 44.6 (X. Уитни, 1932 г.). Если в максимальном плоском графе G каждый 3-цикл является границей некоторой грани, то G — гамилътонов граф.
Как известно (следствие 39.2), всякий максимальный плоский граф 3-связен. Если же такой граф не является 4-связным, то он необходимо содержит 3-цикл, не являющийся границей никакой грани (см. упр. 12 гл. VI).
Пример максимального планарного нега-мильтонова графа G с 11 вершинами приведен на рис. 44.6. Отсутствие гамильтонова
цикла следует из того, что шесть вершин графа G, помеченных знаком «+», попарно не смежны, а на цикле длины 11 могут лежать не более пяти таких вершин. Согласно следствию 44.6, этот граф должен содержать 3-цикл, не являющийся границей никакой грани. Такими 3-циклами являются, например, (а, b, c) и (а, с, d).
Если в n-вершинном графе G фиксировать одну вершину и обход всегда начинать с нее, то всякому гамильтонову циклу очевидным образом будет соответствовать перестановка элементов множества VG. Тем самым найти гамильтонов цикл либо убедиться в отсутствии такого цикла можно путем перебора (n - 1)! перестановок. Если граф G гамильтонов, то проделать этот перебор в полном объеме придется только в случае крайнего невезения — когда нужная, т. е. отвечающая гамильтонову циклу перестановка встретится последней в этом процессе. Если же G — негамильтонов граф, то действуя подобным образом, придется в любом случае проверить все (n-1)! перестановок.
На практике не пользуются столь бесхитростным способом распознавания гамильтоновости, а применяют различные алгоритмы частичного перебора. Однако и там наблюдается такойже эффект— т. е. негамильтоновость становить, как правило, труднее, чем гамильтоновость. В этой ситуации были бы полезны необходимые условия гамильтоновости. Такие условия нужны и для построе-ния примеров негамильтоновых графов с заданными свой-ствами. К сожалению, для графов общего вида необходи-мые условия гамильтоновости неизвестны, за исключе-нием уже упоминавшегося банального факта, что гамиль-тонов граф должен быть 2-связным. Иначе обстоит дело с планарными графами.
Всякую грань плоского графа, граница которой со-держит ровно kребер, назовем k-гранью.
![]() |
![]() |
— грань графа G2, D2 — грань графа G 1 и E G 1 EG2 = EC. Пусть — число k-граней графа G 1 отличных от D2, a fa — число k-граней графа G2, отличных от D1. Очевидно, что
В графе G, изображенном на рис. 44.7, ребра гамиль-тонова цикла С обведены жирными линиями. Граф G 1 включает, помимо цикла С, ребра v1v9, v2v8, v3v7, v4v7, v1v6, а граф G2 — ребра v7v9 и v5v10. В этом примере
f3 =5, f4 = 2, f5 = f6 = 1, f'3 = 4, f'4 = 2, f''3 = f''5 = f''6 =1,
остальные fk, f'k, f''k равны 0.
Возвращаясь к доказательству, установим теперь справедливость равенства (1). С этой целью заметим, что удвоенное число ребер графа G 1 равно, а число всех его граней —. Поэтому, согласно формуле Эйлера, можем написать
![]() |
![]() |
Объединив два последних равенства, получим (1).
Установление негамильтоновости графа путем перебора всех разбиений чисел fk и последующей проверки выполнения равенства (1) едва ли проще полного перебора перестановок, о котором упоминалось выше. Польза теоремы 44.7 в другом — иногда удается, проанализировав числа fk, сразу сделать вывод об отсутствии подходящего разбиения, т. е. вывод о негамильтоновости графа. Рассмотрим в качестве примера граф, изображенный
![]() |
на рис. 44.8. Для этого графа f4 =1, f5 =18, f8 =4, а остальные fk равны 0. Поэтому соотношение (1) должно иметь вид
2 f'4 + 3 f'5 + 6 f'8 = 2 f''4 + 3 f''4 + 6 f''8,
откуда следует, что f'4 = f''4 (mod 3). Это, однако, невозможно, поскольку f'4 + f''4 =f4 =1 Таким образом, нужного разбиения чисел fk не существует, и значит, граф негамильтонов.
Рассмотрим еще один класс теорем о гамильтоновых графах. В этих теоремах утверждается, что если граф G удовлетворяет определенным условиям, то граф, полу-чемый из G с помощью некоторой операции, гамиль-тонов.
Теорема 44.8 (Ф. Харари, С. Нэш-Вильямс, 1965 г.). Реберный граф L(G) гамилътонов тогда и только тогда, когда в графе G имеется цикл, содержащий хотя бы по одной вершине из каждого его ребра.
Из этой теоремы, приводимой здесь без доказательства, вытекает, в частности, что если граф G является эйлеровым или гамильтоновым, то реберный граф L(G) гамильтонов.
Интуитивно ясно, что если граф G порядка п> 3 связен, то при достаточно большом k граф Gk гамильтонов (определение графа Gk см. в § 8). Кроме того, вгамильтоновости графа Gk очевидно следует гамильтоновость графа Gk+l. В связи с этим представляет интерес наименьшее k, при котором граф Gk гамильтонов.
Теорема 44.9 (Д. Караганис, 1968 г.). Если графпорядка п >3 связен, то G3 — гамилътонов граф.
Теорему достаточно доказать для случая, когда - дерево. Будем доказывать следующее, несколько более сильное утверждение: для любого фиксированного ребра аb дерева G граф G3 содержит гамилътонов цикл, походящий через ab. Это утверждение легко проверить непосредственно для деревьев с числом вершин не более четырех. Предположим, что существуют деревья с большим числом вершин, для которых оно не верно. Выберем из них дерево Go с минимальным числом вершин, пусть аb — некоторое ребро дерева Go. При удалении любого ребра Go распадается на два дерева G1 и G2 таких, что aVG, bVG2. По крайней мере одно из них, например G1, содержит не менее трех вершин. Выберем вершину v VG1 так, чтобы ребро va принадлежало EG1.
поскольку \VG1\ < \V Go \, то G1 содержит гамильтонов цикл Н1, проходящий через ребро va.
Теперь рассмотрим дерево G2 Сначала допустим, что \VG2\> З, и пусть bx— ребро графа G2, инцидентное вершине b. Поскольку \VG2\ < \VGo\, то G'3 содержит гамильтонов цикл H2, проходящий через ребро bх. Ис-пользуя циклы H1 и H2, легко построить цикл H в графе G0, проходящий через ab. Для этого достаточно удалить ребра аv и bх из H1 и H2 соответственно и добавить ребра ab и xv, т. е. положить
H = (H1 - va) U (H2 - bx) + xv + аb. Пусть теперь \VG2\ =2, т. е. G2 состоит из одного ребра bc. Тогда положим
H = (H1 — va) + ab + be + vc.
Наконец, если G1 содержит единственную вершину b, то
H=(H1-va)+ab+bv.
Итак, во всех случаях граф G0 содержит гамильтонов цикл H, проходящий через ребро ab дерева G0, что противоречит выбору G0
Легко указать граф, квадрат которого негамильтонов. Таков, например, граф, получающийся из звезды K1,3 подразбиением каждого ребра.
Следующая теорема, приводимая без доказательства, является наиболее значительным результатом среди всех, касающихся гамильтоновых циклов в степенях графов.
Теорема 44.10 (Г. Флейшнер, 1971 г.). Если G — двусвязный граф порядка п>3, то G2 — гамилътонов граф.
Во многих прикладных задачах требуется строить гамильтонову цепь, а не цикл. Граф, содержащий такую цепь, называется трассируемым. Задачи о гамильтоновой цепи и гамильтоновом цикле эквивалентны в том смысле, что, умея решать одну из них, мы смогли бы решить и другую. Эту эквивалентность можно установить с помощью очень простых конструкций. Вместе с исходным графом G, для которого надо решать обсуждаемые задачи, рассмотрим новые графы G' и G" (аb). Граф G' получается добавлением к графу G новой доминирующей вершины, a G" (ab) —добавлением к G двух вершин z и у и пары ребер za и yb (a, b € VG). Теперь легко видеть, что граф G является трассируемым тогда и только тогда, когда граф G' гамильтонов. С другой стороны, очевидно, что гамильтоновость графа G эквивалентна существованию гамильтоновой цепи хотя бы в одном из графов G" (ab), ab € EG. Приведенные конструкции иллюстрируются на рис. 44.9.
Практические применения только что рассмотренного раздела теории графов связаны прежде всего с широко известной задачей коммивояжера. Она состоит в следующем: коммивояжер должен посетить каждый из заданных п городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между каждой парой городов.
Математическая постановка этой задачи выглядит так: в полном взвешенном графе требуется найти гамильтонов цикл (или цепь) минимального веса. Под весом цикла понимается сумма весов составляющих его ребер.
Например, при производстве печатных плат сверлильный станок с числовым программным управлением должен сделать большое количество отверстий в заданных
![]() |
Представление о непосредственных применениях гамильтоновых цепей дает следующая ситуация: имеется машина (станок, компьютер) и п заданий, каждое из которых она способна выполнить после соответствующей настройки. При этом необходимо затратить на перенаводку tij единиц времени для того, чтобы после выполнения i- го задания выполнить j- е. В предположении, что tij = tji, требуется найти последовательность выполнения заданий, при которой время каждой переналадки не пре-восходит величины t. Если построить граф G, у которого
VG={ 1, 2 ,...,n}, EG={ij: tij<t },
то наша задача сведется к отысканию гамильтоновой цепи в этом графе.
В заключение отметим без доказательства теорему, отражающую типичный случай.
Теорема 44.11 (В. А. Перепелица, 1969 г.). Почти все графы гамилътоновы.
Дата публикования: 2015-01-23; Прочитано: 1804 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!