Нарисуем на клетчатой бумаге фигуру, границы которой лежат на сетки.
Посчитаем у этой фигуры клетки внутри нее:
1. Связанные с другими клетками фигуры по одной стороне - обозначим их количество H (одновалентный водород :-) )
2. Связанные с двумя клетками - O (кислород)
3. Связанные с тремя клетками - N (азот)
4. с 4-мя - C (углерод).

Пусть нам дан набор чисел (H,O,N,C) - есть ли алгоритм, который позволит сказать - есть ли фигура, соответствующая этому набору?

С2H5OH что-то не получается нарисовать ;)

(1) синяк )))

(1) плохо старался:

_*_*_
*****
_*_*_

C2H6O - 14 "связей" на 9 элементов, как-то маловато
H2O - 3 "связи" на 3 элемента, нормально.
блин, H3 - то же.
сдаётся мне, алгоритма нет, но доказать непросто. угадал?

(3) связи понять не могу. там же по одной стороне клеток, а у тебя в первой строке два элемента, во второй уже три

http://mathemlib.ru/mathenc/item/f00/s01/e0001285/index.shtml

Первая формула

(4) Н2О 2 связи

(7) "связи" я сказал ;) 2*1+2 - четыре выходит

(5) так понятнее?
https://docs.google.com/drawings/pub?id=1_510WrVBXPyChQDKmAmMLiZfhEKJn1LdtGUARx63wkk&w=960&h=720

(9) значительно. ну ты и сравнил с лягушкой из (3) ;)

(0) Может быть матрица с "ножками"-валентностями и далее - транспортная задача / задача о назначении персонала?

Только наложить запрет на соединение "себя с собой". http://cyclowiki.org/wiki/Транспортная_задача

(8)H - O - H

где тут 3 связи? или 4-ре?

(13) сумма валентностей, если угодно. 2*H+O

(14)ну связи то 2, причем тут сумма валентности. черточек 2, или мы о чем-то разном?

похоже что алгоритм есть только выводить его нудно...
- всего связей в фигуре четное число,
- зависимость #(H), #(O), #(N), #(C) друг от друга (в связи с "геометричностью" фигуры в квадрате)

+вопрос: фигура связная? (допустим ли Н4 как ** ** ?)
если нет то можно и нарисовать что-либо попытаться

+(12) И запреты нижнего треугольника, для исключения дублей типа АБ-БА

(9) Там формула СН3-О-СН3, а это не С2Н5-ОН.
И вообще есть понятие изомеров - одно и то же количество атомов, НО разная геометрия. В химии это существенно - разные свойства -> разные вещества.

+(19) Да. Правильная картинка для (9) будет такая:
http://upload.wikimedia.org/wikipedia/commons/3/37/Ethanol-2D-flat.png

(20) Таки ДА!
Поэтому формулировка задачи в (0) неполна, ибо одной формулы, то есть списка атомов и их количества МАЛО! Нужна еще геометрия.
Или в ответе - все изомеры, но тогда только математики маловато, там еще + химия: что с чем как можнет соединяться, валентные связи и прочее...
Может в чем-то неправ, химию читал ОЧЕНЬ давно.

(21) Мне кажется, что задача в (0) к химии отношения не имеет.

(0) а как быть с серой? Там валентность от 4 до 7.

(0) Если набор клеток представляет из себя "односвязную" фигуру и количество клеток ограничено, то такой алгоритм создать можно. Если количество клеток не ограничено, то алгоритм создать нельзя.

(22) +100!
тут "своя химия"

(24) дано конечное количество клеток

ах.еть как некоторым нечем заняться...
(0) ты что, школьник которому тупо скучно на уроке?

Вот некоторые быстропроверяемые обязательные условия:
1. Условие азотно-водородной четности: числа N и H име

Вот некоторые быстропроверяемые обязательные условия:
1. Условие азотно-водородной четности: числа N и H имеют одинаковую четность
2. Условие водородной ограниченности: H<=N+2*C+2

(27) типа того ))

Забавно. По ссылке в (6) кто нибудь ходил????

(31) ходил, там общая теория, без специфики

(29) Это ответы?

(33) нет, это небольшой шаг к решению

(32)
>>Примером результата о существовании графов с фиксированными свойствами может служить критерий реализуемости чисел степенями вершин некоторого графа: набор целых чисел 0 ? d1 ? d2 ? ... ? dn, сумма которых четна, можно реализовать степенями вершин графа без петель и кратных ребер тогда и только тогда, когда для любого r(1 ? r ? n - 1) выполняется условие:

Далее дана формула. Увы написать ее здесь не могу.

В конкретном случае выписываем набор чисел: 1,1,...,2,2,...,3,3,...,4,4,...4

Проверяем этот набор по формуле.

(35) ну в общем это тоже необходимое, но недостаточное условие
например граф тетраэдр (4 вершины, каждая соединена с каждой) существует, но в данной модели нереализуем

(36) А если добавить условие E<=N^2/4? Где N количество элементов. E количество ребер (сумма валентных связей деленная пополам).

E<=N^2/4 это необходимое уловие существования графа без треугольных циклов.

Тогда тетраэдр не проходит.
3,3,3,3
N=4 E=6
6>4*4/4=4

Условий (35) и (37) мало.

Например C2H6 удовлетворяет этим условиям. Но прикрепить 6 водородов, так чтобы они не касались друг друга невозможно.