граф может быть без рёбер?

[bigarcus]

Математический граф определяется как пара множеств: множество вершин и множество ребер.
Множество вершин по определению является непустым.
А про множество ребер такого замечания нет.

Правильно ли я тогда понимаю, что следующие объекты $G$, $H$, $J$ являются графами:
?

[ИСН]

Ну да, а что такого? Понятие связности ведь зачем-то же введено? Значит, её может не быть? Может.

[Aritaborian]

Да, являются.

[bigarcus]

Спасибо. (связность я ещё не проходил)

А по определениям мультиграфа, псевдографа, орграфа.
Правильно ли я понимаю, что просто три параметра перебираются: кратные дуги, петли, ориентация.

То есть так, верно:
?

[provincialka]

А разве в обычном графе петель быть не может? Как же тогда рефлексивные отношения изображать?

[bigarcus]

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

Могу ошибаться. Прошу поправить, если что.

[provincialka]

В простом графе нет петель. Но если в графе петли есть, это не обязательно псевдограф. Я понимаю так: ребра - это подмножество декартова произведения $V\times V$ (для ориентированного графа). Если граф неориентированный, то каждая пара $(a,b)$ отождествляется с $(b,a)$, что никак не мешает присутствию в графе пар вида $(a,a)$.

Конечно, это все вопрос соглашения. Но я привыкла использовать графы для изображения отношений. И без петель там пришлось бы туго! Практически все основные типа отношений (эквивалентность, толерантность, нестрогий порядок) - рефлексивны, то есть включают в себя пары $(a,a)$. Честно говоря, не слышала, чтобы для их описания использовались "псевдографы".

-- 21.01.2014, 03:20 --

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

[bigarcus]

provincialka в сообщении #817256 писал(а):

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

Дык псевдограф и есть граф с петлями, но без кратных ребер (и без ориентации).
С петлями и с кратными ребрами это будет псевдомультиграф.

Опять же, я скорее спрашиваю, чем утверждаю. Но я так понял.

[provincialka]

Ну, я набрала в поиске "псевдограф", везде написано, что это мультиграф с петлями. А вообще это все неважно. Даже в небольшой статье в начале можно указать текущее понимание терминов.
Кстати, а почему в ориентированном графе нельзя ввести петли? Как я тогда антисимметричное отношение буду изображать? Пожалуй, мне не нравится ваша табличка, в которой "плюсики" только по диагонали. Разве не возможны и другие комбинации?

[arseniiv]

В случаях нескольких плюсов можно было бы написать что-то типа мультиорграф, псевдоорграф, псевдомультиграф и псевдомультиорграф. Но лучше явно всё это определить перед местом использования, согласен.