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

[Rayman]

Здравствуйте, помогите пожалуйста.
Мне для решения моей задачи необходимо создать матрицу инцидентности. Входные данные пары цифр(не повторяются), пример 3 4, 2 3, 4 5, 1 2. Т.е. должен получиться ориентированный граф, 1->2->3->4->5. Если необходимо, во входных данных можно добавить ещё кол-во пар, или сколько всего цифр. Заранее спасибо!

[Olejik]

ну вообще это легкая задача, для начала надо принять количество вершин:

scanf("%d",kolVer);

потом уже зделать цикл, но еще обьявить двумерный массив:

int graph[100][100];

а вот теперь цикл:

for(int i = 0 ; i < kolVer ; i++)
{
 for(int j = 0 ; j < kolVer ; j++)
 {
  if(i == j)
  {
   continue;
  }
  //а вот здесь все делаем, нужен еще массив вершин, которые мы
  //прошли и к которым уже нельзя возвращаться, ну можно функцию
  //зделать, которая будет возвращать 0 при вершине которую мы еще не
  //прошли, иначе 1, т.е. ее пропускать.
 }
}

[Rayman]

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

[Olejik]

Вы не понимаете как дать понять программе чтобы она зltлала такую матрицу?:
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

[Rayman]

На сколько я знаю, в матрице инцидентности ещё присутствует -1, т.е. 1 значит что связь j «выходит» из вершины i, а -1 связь «входит» в вершину. Мне не понятно как непосредственно из моих входящих данных построить такую матрицу, тем более, что мб такой случай 5 4, 4 2, 2 1. И соответственно искомая очередь будет 5-4-2-1. Как мне в таком случаи пронумеровать столбцы матрицы?

[Olejik]

ну я фиг знает, когда я курсовик делал на тему "2-х связные компоненты", я обходил граф в глубину и у меня была сначало матрица инцидентности и в университет нам ее показывали и у меня был зачот и попадался вопрос как можно представить граф. Там была матрица инцидентности, если стоит 1, то значит связь существует, если 0, то связи нету. Ну можно конечно представить и -1, типа связи нету, нету разницы. А строить такую матрицу легко, типа i -это одна вершина, j - другая, если Вы хотите чтобы вершина 1 была смежна с вершиной 3, то в матрице инцидентности пишите вот так вот:
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
это у нас ориентированный граф, т.е. 1 -> 3, если бы было вот так вот:
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
то это неориентированный граф. Ну а если Вам нравится -1, то вместо 0 можете представить -1.

[Rayman]

Странно, нас учат немного по другому, например дано следующее 2->4, 3->2, 4->6. А матрицу инц. для этого случая я представляю себе так:
| 2 4 3 6
--------------
1| 1 -1 0 0
2| -1 0 1 0
3| 0 1 0 -1
Это матрицу я попробовал нарисовать, столбцы - все возможные цифры, строки - номера пар. У меня проблема в том, что я не понимаю как в цикле передвигаться по столбцам, когда они вот таким например образом "пронумерованы".
Матрица немного косая вышла, но думаю смыл должен быть ясен)

[Olejik]

если я правильно понял с матрицей инцидентности, то:
в столбце у тебя (1,2,3) - вершины, а в строке (2,4,3,6) - ребра. Если (1,2) = 1, то значит вершина 1 есть начало ребра 2, а вот вершина 2 является концом ребра 2. Так?

[Rayman]

Вроде так.+)

[Olejik]

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