asault_ceko

Типо ето же окружность...

Нет, сечение вашей фигуры плоскостью z=const - это сегмент круга, ограниченный полуокружностью x^2+y^2=9 (y>=0) и хордой y=z. Его площадь от z зависит. Подставляйте формулу для площади этого сегмента (это и будет S(z)) и интегрируйте ее по z от 0 до 3.

Внутренние циклы выполняют суммарно максимум 8(r-l-1) операций. На каждой итерации внешнего цикла r-l уменьшается на 2. Т.е. всего операций будет 8(n-2)+8(n-4)+8(n-6)...

Можете эту арифметическую прогрессию подсчитать и оценить?

Может эта статья вам поможет

Твой граф стягивается в К33, т.е. он не планарный. Если я правильно понял принцип стягивания.

Конкретно, тебе требуется:
1) стянуть в одну вершину три самые правые.
2) стянуть ребро малого равностороннего треугольника, которое пересекается другим ребром.
3) никогда больше не выкладывать сюда граф, у которого вершины не обозначены буквами или числами, потому что это пипец как их описывать!!

Если вы уверены, что он планарный, то его надо нарисовать без пересечений ребер. Подвигайте вершины туда-сюда.

А теоремы эти используют как раз, чтобы доказать, что граф не планарный. Тогда вы берете как-то стягиваете его вершины и получаете K33 или K5. Значит не планарный.

Доказать отсутствие таких стягиваний очень муторно. Надо перебирать все варианты. Типа, что будет если мы вот эти 2 вершины стягиваем в одну? А если нет? В первом случае, а стягиваем ли мы туда вот эту третью? А если нет? И так у вас 100500 случаев. Если очень граматно выбрать вершины, то есть шанс, что количество вариантов будет не слишком большое. Если видите, что стянутый граф можно нарисовать без самопересечений, дальше стягивать не надо.

Смотрите критерии планарности - надо плясать от них.

Например, если взять первый критерий - граф не содержит подгарфа, который есть подразделение K5 или K3,3.

Очевидно, что n=4 всегда планарен сам граф. Доказывать нечего. Остались случаи n=5,6,7.

Если сам граф не содержит такого - то он уже планарен, доказывать нечего. Если же сам граф содержит K5 или K3,3 то вам надо доказать, что дополнительный граф не может содержать такие подграфы.

n=8, очевидно, тут не подходит, потому что можно взять K5, прикрутить к нему рядом K3 (Без новых ребер между кликами). Дополнительный граф при этом будет K5,3 - который содержит в себе K3,3.

Советую рассмотреть 3 случая и доказать что они все не возможны. Граф и дополнительный граф содержат по K5; оба содержат по K3,3; один содержит K5, а другой K3,3.

Например, первый случай весьма прост - при n<8 подграфы пересекаются как минимум по 3 вершинам. В прямом графе из-за K5 они обязаны иметь между собой ребра, а из-за K5 в дополнительном графе - они обязаны не иметь между собой ребер. Противоречие.