Есть таблица с двумя полями - id и connectedids. Каждая запись в этой таблице - вершина графа.
Поле  id определяет порядковый номер вершины графа, а connectedids содержит целые числа разделенные запятыми, определяющие idы других вершин, соединенные с даной вершиной.

Например:
1 - 2,4
2 - 1,3,4
3 - 2,4
4 - 3,1,2

Как проверить и исправить ошибки в записи этого графа?
Т.е. если первая вершина соеденена с 4й, то и 4я должна быть соеденена с первой. Если в connectedids четвертой нет первой, то такую запись надо добавить.

Как удалить вершину графа?
Вместе с удалением всей записи вершины, удалить из connectedids других вершин все ссылки на удаленную

Никак не могу придумать оптимального алгоритма с минимальным количеством запросов в базу.   Помогите.   

У тебя изначально информация не верно хранится. Надо хранить отдельно родителей, отдельно предков.
Плюс, задача проверки - какая? Графы разгные бывают и замкнутые в том числе.
И вообще, задача на практике - какая?

Что-то не поняла идею. 

Я бы предложила хранить отдельно врешины, отдельно ребра. Поскольку по условию задачи граф не ориентированный, то каждое ребро достаточно хранить один раз. Если уже записали (1,4), не нужно писать (4,1). Тогда и такая проверка на ошибки записи не нужна. А ответственность за целостность данных (удаление ребер, при удалении инцидентных им вершин) можно возложить на саму базу, если использовать foreign keys, указав ON DELETE CASCADE 

Идея - дерево.
Тут главное, чтобы автор пояснил свою задачу в абстрактном изъяснении... А иначе будем гадать что и как. Дерево тож не везде сгодится.

Mal Hack, идея не понятна по другому, допустим есть:

Тут у элемент 1 - корень дерева, у элемента 2 - родитель 1, а у элементов 3 и 4 - родитель 2.
Те хранить отдельно родителей и детей не получится - задача поставлена не верно.
Причем условием является хранение графа, а не дерева, как его частного случая.

Я сказал: "хранить родителей и детей отдельно для КАЖДОЙ вершины или единицы графа". Это совершенно другой смысл.

А, в смысле, надо было читать, отдельно родителей, отдельно ДЕТЕЙ. Так ясно.  Дерево хорошо тем, что для него есть подробно разработанные схемы обхода. Но, как Вы справедливо заметили, не подойдет для графа с циклами. В общем-то, для неориентированного графа понятия родителей и детей - несколько искуственное, только для обхода и имеет смысл. Но Вы правы, лучше подождать разъяснения автора темы о характере задачи, тогда можно будет отбирать более рациональный вариант

Mal Hack, 
Это не рационально - допустим три связанные вершины - в худшем случае получится 3 таблицы - в одной все предки 1 вершины, во второй все предки второй и тд
В лучшем случае получится таблица предков и таблица родителей с дублированной информацией.

Вот есть такая идея:
http://forums.lavag.org/index.php?showtopic=3250
воообщем-то тоже самое, что сказала Golda

Объясняю суть задачи.
Требуется доработать проект большой энциклопедии, а именно добавить функцию списка "смотри также".
Т.е. каждая статья является вершиной графа. А в отдельном поле каждой статьи храняется связанные с ней по смыслу статьи. Понятное дело, что если 4я статья ссылается на 107ю, то и 107я должна ссылаться на 4ю.
Такой метод хранения был выбран поскольку акцент делается именно на незамедлительный просмотр связанных статей.

WolfON, еще раз посмотри на мою фразу: "Я сказал: "хранить родителей и детей отдельно для КАЖДОЙ вершины или единицы графа". Это совершенно другой смысл. " 

Ты не понимаешь меня ;)


Sunvas, тебе нужно как раз дерево, причем все рализовывается намного проще, чем ты думаешь.
Скажи, как храняться сами статьи в базе и должны ли показываться ссылки на "похожие" страницы, когда мы смотрим 4 статью, а для нее "похожая" 119, а для нее - 136, более глубоки по уровню "похожести"?

Статьи хранятся в одной таблице, со структурой:

id - номер статьи
title, contenet, [другие служебные поля]
seealso - вот тут мы через запятую и храним ссылки на другие статьи

Есть возможность сделать еще одну таблицу из двух полей или обязательно надо обойтись полем seealso?

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

Я бы сделал так.
Делаем таблицу из двух полей. Оба поля содержат ID статей.
Соотвественно в эти поля заносим два ID дву статей, которые "похожи" друг на друга.
Соответственно, когда надо достать список, делаем
SELECT `*` FROM myt WHERE id1 = $id OR id2 = $id.
Так получим список ID статей, которые так или иначе "похожи" на нашу.
Причем надо будет потом, из него (мы же получим матрицу из двух столбцов и n строк) сделать один массив, откуда удалить повторяющиеся (по хорошему этого быть не должно, надо следить за повторами на этапе добавления связи).
Затем делаем SELECT `*` FROM myt WHERE id1 IN ($mylist) OR id2 IN ($mylist).
Это уже два этапа вложенности, думаю хватит.
Проверок соответственно уже не надо делать, а саязана ли 4 с 3, если 3 связана с 4.

Хм. Я подумаю над таким вариантом. Однако статей в энциклопедии действительно много, за быстродействие опасаюсь. Нужен только один уровень вложенности.