Матрица инцидентности

[mr.daos]

Всем привет!
В задаче по теории графов дана была матрица инцидентности орграфа и нужно было по ней изобразить сам орграф. Но некоторые элементы (помимо -1, 0, 1) было больше 1. Как такое может быть? Ведь согласно определению матрицы инцидентности, там могут быть только числа -1, 0, 1.

[vpb]

mr.daos в сообщении #1497263 писал(а):

Как такое может быть? Ведь согласно определению матрицы инцидентности, там могут быть только числа -1, 0, 1.

А на какое определение матрицы инцидентности (и графа заодно; а то ведь оне тоже разные бывают: самые обычные --- неориентированые, без петель и кратных ребер; а бывают ориентированые, и с петлями, и с кратными ребрами ...) Вы опираетесь ? И на какую книжку (или это методичка какого-то конкретного вуза, остальным недоступная, или просто лекции) ?

[mr.daos]

vpb в сообщении #1497269 писал(а):

А на какое определение матрицы инцидентности (и графа заодно; а то ведь оне тоже разные бывают: самые обычные --- неориентированые, без петель и кратных ребер; а бывают ориентированые, и с петлями, и с кратными ребрами ...) Вы опираетесь ? И на какую книжку (или это методичка какого-то конкретного вуза, остальным недоступная, или просто лекции) ?

Задачу скинул знакомый, который попросил помочь, поэтому что у него возник такой же вопрос. Опираюсь на стандартное определение матрицы инцидентности орграфа (и самого орграфа), найденное в интернете: элемент $a_{i,j}$ равен 1, если вершина $i$ инцидентна ребру $j$ и является его началом, -1, если является концом и 0, если они не инцидентны.

[kotenok gav]

del, я действительно перепутал матрицы смежности и инцидентности.

[mr.daos]

kotenok gav в сообщении #1497287 писал(а):

Судя по всему, $a_{ij}=k>0$ значит, что из вершины $i$ в вершину $j$ исходит $k$ рёбер. Но непонятно, почему $a_{ij}=-a_{ji}$ не для всех $i$ и $j$...

Вы, видимо, описали матрицу смежности

[popolznev]

mr.daos в сообщении #1497278 писал(а):

элемент $a_{i,j}$ равен 1, если вершина $i$ инцидентна ребру $j$ и является его началом, -1, если является концом и 0, если они не инцидентны.

А часто бывает и наоборот! В этой теории графов, как и во всей т. н. дискретной математике, большой разнобой в обозначениях и терминологии.

[Утундрий]

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

[vpb]

mr.daos в сообщении #1497278 писал(а):

Задачу скинул знакомый, который попросил помочь, поэтому что у него возник такой же вопрос. Опираюсь на стандартное определение матрицы инцидентности орграфа (и самого орграфа), найденное в интернете: элемент $a_{i,j}$ равен 1, если вершина $i$ инцидентна ребру $j$ и является его началом, -1, если является концом и 0, если они не инцидентны.

В столь неопределенной ситуации и совета никакого определенного дать нельзя. Разве что узнать, по какой книжке "знакомый" занимается, и т.д. А искать "стандартные определения" в интернете --- вредно. Не понимаешь, о чем вообще речь идет --- не берись помогать.

[Lia]

mr.daos
Матрицы замечательно набираются с помощью LaTeX. Рекомендую. Картинкам свойственно испаряться со временем.

[arseniiv]

Ну если глянуть на эту матрицу одним глазком, то видно, что или ребру соответствуют две вершины с нормальными индексами инцидентности ±1, или одна с каким-то большим. Единственное разумное конструктивное предположение для таких случаев — это что там кратные петли указанной кратности. Да, получается очень странный граф, но ведь это лишь один граф, и может для других попадаются и кратные рёбра, не являющиеся петлями, и некратные петли.