2 svar
114 visningar
Marx behöver inte mer hjälp
Marx 361
Postad: 23 feb 2022 11:55 Redigerad: 23 feb 2022 12:15

Adjacency matrix

Hej,

Kan någon förklara varför det går att rita en adjacency matris för en graf med n noder på n! olika sätt?

Jag tänker att det bör vara fler då varje position (i,j) har två möjligheter, antingen 1 eller 0, och då har vi 2n2möjligheter. Men eftersom diagonalen är som en symmetrisk linje mellan övre delen och nedre delen av matrisen så är de delarna identiska. Vi har diagonalen också som innehåller endast nollor. Då bör antalet olika matriser bli 2n(n-1)2

nigus 52
Postad: 23 feb 2022 12:19 Redigerad: 23 feb 2022 12:22

Det är lite oklart vad som menas med "rita på olika sätt" i det här sammanhanget, men jag gissar att det har med labellings att göra. Om du till exempel har grafen

1 - 2 - 3

så har den adjacencymatris 010101010

men om vi ändrar labelling till

2  -  1  -  3

så blir det 011100100

Och det finns ju n! olika labellings, så det kanske är svaret du är ute efter? Men det kan ju vara så att olika labellings ger samma adjacency matris, till exempel blir  3  -  2  -  1 samma som i första exemplet. Så i det avseendet blir det färre än n! matriser (generellt tror jag det blir n!/A(G) där A(G) är antalet automorfier av grafen? inte 100% säker).

 

 

EDIT: av någon anledning såg jag inte andra stycket i ditt inlägg först, sorry. Du har rätt att antalet matriser över alla möjliga grafer borde bli 2^(n(n-1)/2). Jag tolkade det första stycket som att vi vill räkna antalet sätt att skriva adjacency matris för en fix graf

Marx 361
Postad: 23 feb 2022 12:27 Redigerad: 23 feb 2022 12:29
nigus skrev:

Det är lite oklart vad som menas med "rita på olika sätt" i det här sammanhanget, men jag gissar att det har med labellings att göra. Om du till exempel har grafen

1 - 2 - 3

så har den adjacencymatris 010101010

men om vi ändrar labelling till

2  -  1  -  3

så blir det 011100100

Och det finns ju n! olika labellings, så det kanske är svaret du är ute efter? Men det kan ju vara så att olika labellings ger samma adjacency matris, till exempel blir  3  -  2  -  1 samma som i första exemplet. Så i det avseendet blir det färre än n! matriser (generellt tror jag det blir n!/A(G) där A(G) är antalet automorfier av grafen? inte 100% säker).

 

 

EDIT: av någon anledning såg jag inte andra stycket i ditt inlägg först, sorry. Du har rätt att antalet matriser över alla möjliga grafer borde bli 2^(n(n-1)/2). Jag tolkade det första stycket som att vi vill räkna antalet sätt att skriva adjacency matris för en fix graf

Du har förstått frågan korrekt att vi vill räkna antalet sätt att skriva adjacency matris för en graf. Tack för din förklaring.

Jag själv kom ju på en liknande förklaring dock genom att koppla grafernas utseende till deras respektive matriser för en graf med 3 noder. Och då kom jag fram till samma resultat som ditt, att det måste vara n! sätt att rita adjacency matriser för en fix graf. Man kan självklart generalisera det för n noder också.

Svara
Close