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 $2^{n^{2}}$ mö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 $2^{\frac{n (n - 1)}{2}}$ .

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 $[\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}]$

men om vi ändrar labelling till

2 - 1 - 3

så blir det $[\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix}]$

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

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 $[\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}]$

men om vi ändrar labelling till

2 - 1 - 3

så blir det $[\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix}]$

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 Avbryt