. Помимо того, что она сама весьма занимательна, я уже сбился со счёта, какую новую задачу она порождает. (Если кого наш PolyminoLab подзадолбал, можете дальше не читать )
На бумаге в клеточку написуем прямоугольник AxB. Какова может быть максимальная длина (в клетках) внутренних стенок, при котором область останется связной (из любой клетки можно попасть в любую другую)?
Нужна формула и более-менее убедительное доказательство. Мне кажется, у меня есть и то и другое.
P>На бумаге в клеточку написуем прямоугольник AxB. Какова может быть максимальная длина (в клетках) внутренних стенок, при котором область останется связной (из любой клетки можно попасть в любую другую)?
Нуу,.. сегодня что-то совсем просто ...
Число внутренних границ между клетками A(B-1)+B(A-1)=2AB-A-B,
Число границ между клетками, которые должны остаться незакрытими,
найдем из следующих соображений: представим что клетки — вершины
графа ( AB вершин ). Тогда чтобы его связать надо AB-1 связей —
это число границ, которые должны остаться не перегороженными.
Следивательно число перегородок: A(B-1)+B(A-1)-(AB-1)=AB-A-B+1=(A-1)(B-1).
P>На бумаге в клеточку написуем прямоугольник AxB. Какова может быть максимальная длина (в клетках) внутренних стенок, при котором область останется связной (из любой клетки можно попасть в любую другую)?
P>Нужна формула и более-менее убедительное доказательство. Мне кажется, у меня есть и то и другое.
И мне кажется, что у меня есть и то и другое, а также кажется что и у тебя тоже есть и то и другое.
Следовательно, у меня кажущихся вещей в два раза больше.
1) Верхняя оценка.
Для связности лабиринта необходимо, чтобы каждая его клетка
имела не менее 2 открытых граней. Кроме того, у двух клеток
допустимо наличие только по одной открытой грани - в них
путь начинается и заканчивается. А так же, каждая внутрення
стенка принадлежит двум клеткам. Тогда
Lmax = (2АВ - 2(А + В) + 2) / 2 = АВ - (А + В) + 1
2) Такие лабиринты существуют, например
+-----------+
| |
|---------- |
| |
| ----------|
| |
|---------- |
| |
+-----------|
Здравствуйте, mrhru, Вы писали:
M>Чем смог — помог.
M>1) Верхняя оценка. M>Для связности лабиринта необходимо, чтобы каждая его клетка M>имела не менее 2 открытых граней. Кроме того, у двух клеток M>допустимо наличие только по одной открытой грани — в них M>путь начинается и заканчивается.
Вполне допустимы лабиринты, где более двух тупиков. Тем не менее мне кажется это нормальным путём, просто рассуждения надо провести поаккуратнее... Но гениально простое решение от Chorkov делает их ненужными.
Здравствуйте, Pushkin, Вы писали:
M>>1) Верхняя оценка. M>>Для связности лабиринта необходимо, чтобы каждая его клетка M>>имела не менее 2 открытых граней. Кроме того, у двух клеток M>>допустимо наличие только по одной открытой грани — в них M>>путь начинается и заканчивается.
P>Вполне допустимы лабиринты, где более двух тупиков. Тем не менее мне кажется это нормальным путём, просто рассуждения надо провести поаккуратнее...
Согласен.
P>Но гениально простое решение от Chorkov делает их ненужными.
P>...клетки — вершины графа ( AB вершин ). Тогда чтобы его связать надо AB-1 связей
P>Вот это неплохо бы доказать для полного счастья
Что именно доказать?
То, что дерево — это связный граф без циклов, т.е. у дерева число связей минимально?
Или то, что в дереве с N вершинами N-1 связь, что доказывается по индукции?
Здравствуйте, mrhru, Вы писали:
M>Или то, что в дереве с N вершинами N-1 связь, что доказывается по индукции?
Имелось в виду утверждение: для того, чтобы граф с N вершинами был связным в нём должно быть как минимум N-1 связь. Оно не так очевидно, как кажется — разговоров о цепочках маловато будет. Но ты уже произнёс ключевое слово "индукция", поэтому считай, что я успокоился
Здравствуйте, Pushkin, Вы писали:
P>Имелось в виду утверждение: для того, чтобы граф с N вершинами был связным в нём должно быть как минимум N-1 связь. Оно не так очевидно, как кажется — разговоров о цепочках маловато будет. Но ты уже произнёс ключевое слово "индукция", поэтому считай, что я успокоился
Могу успокоить и без индукции:
Предположим есть граф. Если мы сольем две вешины соединенные ребром, то получим граф с тем же числом связных компонент. При этом число вершин уменьшится на 1, а ребер, как минимум на 1. Очевидно, что такую операцию мы можем продолжать до "схлопывания" графа в точки, соответствующие связным компонентам. Отсюда — количество ребер в графе, как минимум N-S, где S число связных компонент.
P>На бумаге в клеточку написуем прямоугольник AxB. Назовем "комнатой" прямоугольник со сторонами >=2 не содержащий внутри себя стенок. Какова может быть минимальная длина (в клетках) внутренних стенок, при котором прямоугольник не содержит "комнат"?
Здравствуйте, MichaelP, Вы писали:
MP>Предположим есть граф. Если мы сольем две вешины соединенные ребром, то получим граф с тем же числом связных компонент. При этом число вершин уменьшится на 1, а ребер, как минимум на 1. Очевидно, что такую операцию мы можем продолжать до "схлопывания" графа в точки, соответствующие связным компонентам. Отсюда — количество ребер в графе, как минимум N-S, где S число связных компонент.
PS
IT опять что-то нахимичил с оценками, так что приходится обходиться значками
Здравствуйте, MichaelP, Вы писали:
MP>Опять же навеяло P>>
P>>На бумаге в клеточку написуем прямоугольник AxB. Назовем "комнатой" прямоугольник со сторонами >=2 не содержащий внутри себя стенок. Какова может быть минимальная длина (в клетках) внутренних стенок, при котором прямоугольник не содержит "комнат"?
1) Если в лабиринте нет комнат 2х2, то нет и комнат больших размеров.
1.5) Необходимо так поставить стенки, чтобы любая комната была разрушена.
2) В лабиринте АхВ без внутренних стенок - возможных комнат 2х2 - (А - 1) * (В - 1)
3) Установкой одной стенки мы можем разрушить не более двух комнат
4) Итого стенок требуется не менее
Lmin = (А - 1) * (В - 1) / 2
Например, для лабиринта 3х3:
+-----+
|* * *|
| |
|*|*|*|
| |
|* * *|
+-----+
M>1) Если в лабиринте нет комнат 2х2, то нет и комнат больших размеров.
M>1.5) Необходимо так поставить стенки, чтобы любая комната была разрушена.
M>2) В лабиринте АхВ без внутренних стенок - возможных комнат 2х2 - (А - 1) * (В - 1)
M>3) Установкой одной стенки мы можем разрушить не более двух комнат
M>4) Итого стенок требуется не менее
M> Lmin = (А - 1) * (В - 1) / 2
M>Например, для лабиринта 3х3:
M>+-----+
M>|* * *|
M>| |
M>|*|*|*|
M>| |
M>|* * *|
M>+-----+
M>
Ну просто округляй в большую сторону и всё.
mrhru совершенно прав — одной стенкой убиваем две соседние (частично перекрывающиеся) комнаты. Если нарисовать сетку из (A-1)x(B-1) точек, где каждая символизирует комнату, а связь их перекрытие, то надо просто убирать последовательно пары связанных комнат. Не видо, что бы нам могло препятствовать это делать, если только в самом конце одна комната останется, так её отдельно покоцать.
Итак ответ (A-1)*(B-1)/2 с округлением вверх.
Для 4х4 это будет 3*3/2=5
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, mrhru, Вы писали:
M>>
M>>1) Если в лабиринте нет комнат 2х2, то нет и комнат больших размеров.
M>>1.5) Необходимо так поставить стенки, чтобы любая комната была разрушена.
M>>2) В лабиринте АхВ без внутренних стенок - возможных комнат 2х2 - (А - 1) * (В - 1)
M>>3) Установкой одной стенки мы можем разрушить не более двух комнат
M>>4) Итого стенок требуется не менее
M>> Lmin = (А - 1) * (В - 1) / 2
M>>Например, для лабиринта 3х3:
M>>+-----+
M>>|* * *|
M>>| |
M>>|*|*|*|
M>>| |
M>>|* * *|
M>>+-----+
M>>
MP>А 4х4?
Мдя.
Немного по другому (в свете модных нынче графов )
Необходимо устранить в исходном графе все циклы длины 4.
Например, для комнаты 5х5, граф будет в виде,
Разрывы всех циклов длиной 4 — это замощение этого клетчатого поля домино.
Если количество клеток нечетно (когда (А — 1) * (В — 1) нечётно), необходимо
добавлять ещё одну стенку, поэтому
M>Немного по другому (в свете модных нынче графов ) M>Необходимо устранить в исходном графе все циклы длины 4. M>Например, для комнаты 5х5, граф будет в виде, M>
M>где + это центры комнат.
M>Разрывы всех циклов длиной 4 — это замощение этого клетчатого поля домино. M>Если количество клеток нечетно (когда (А — 1) * (В — 1) нечётно), необходимо M>добавлять ещё одну стенку, поэтому M>
M> Lmin = floor((А - 1) * (В - 1) / 2)
M>
С вестибулярным аппаратом немного не в порядке (пол с потолком перепутал)
А так решение лучше чем мое