| dbo:abstract
|
- في نظرية المخططات و علوم الكمبيوتر، مصفوفة المجاورة (بالإنجليزية: Adjacency Matrix) هي مصفوفة مربعة تستخدم لتمثيل . عناصر المصفوفة تعكس ما إذا كانت رؤوس الرسم البياني (vertices) متجاورة ومرتبطة أم لا. (ar)
- Una matriu d'adjacència és una matriu quadrada que s'utilitza com una forma de representar relacions binàries. (ca)
- Matice sousednosti je v matematice a informatice používaný způsob reprezentace grafu. Pro konečnou množinu vrcholů grafu G, kterých je n, má podobu čtvercové matice n×n, jejíž hodnota na místě aij je celé číslo odpovídající počtu hran vedoucích z vrcholu i do vrcholu j. Prvky na tak obvykle odpovídají počtu hran vedoucích z vrcholu i do vrcholu i (takové je běžná konvence u orientovaných grafů), ovšem někdy se na diagonálu ukládá dvojnásobek této hodnoty (taková bývá konvence u neorientovaných grafů). Pro každou třídu existuje až na prohazování řádků a sloupců právě jedna matice sousednosti a ta neodpovídá žádné jiné třídě. (cs)
- Στα μαθηματικά και στην επιστήμη υπολογιστών, ο πίνακας γειτνίασης χρησιμοποιείται για να αναπαραστήσει τις κορυφές ενός γράφου, οι οποίες συνδέονται με άλλες κορυφές. Ένας άλλος πίνακας αναπαράστασης του γράφου είναι ο πίνακας προσπτώσεων. Συγκεκριμένα, ο πίνακας γειτνίασης ενός πεπερασμένου γράφου G με n κορυφές είναι ο πίνακας διαστάσεων n × n όπου το μη διαγώνιο στοιχείο aij είναι ο αριθμός ακμών από την κορυφή i στην κορυφή j, και το διαγώνιο στοιχείο aii, είναι ανάλογα με τη σύμβαση είτε ο αριθμός είτε το διπλάσιο των ακμών (βρόχοι) από την κορυφή i στον εαυτό της. Σε μη κατευθυνόμενους γράφους συνήθως χρησιμοποιείται η δεύτερη σύμβαση (το διπλάσιο του αριθμού των βρόχων), ενώ σε κατευθυνόμενους γράφους κατά κανόνα χρησιμοποιείται η πρώτη σύμβαση. Υπάρχει μοναδικός πίνακας γειτνίασης για κάθε κλάση ισομορφισμού γράφων και είναι διάφορος του πίνακα γειτνίασης οποιασδήποτε άλλης κλάσης ισομορφισμού γράφων. Στην ειδική περίπτωση ενός πεπερασμένου απλού γράφου, ο πίνακας γειτνίασης είναι ένας (0,1)-πίνακας με μηδενικά στοιχεία στη διαγώνιό του. Αν ο γράφος είναι μη κατευθυνόμενος, ο πίνακας γειτνίασης είναι συμμετρικός. Η σχέση μεταξύ ενός γράφου και των ιδιοτιμών και ιδιοδιανυσμάτων του πίνακα γειτνίασής του μελετάται στη φασματική θεωρία γράφων. (el)
- Eine Adjazenzmatrix (manchmal auch Nachbarschaftsmatrix) eines Graphen ist eine Matrix, die speichert, welche Knoten des Graphen durch eine Kante verbunden sind. Sie besitzt für jeden Knoten eine Zeile und eine Spalte, woraus sich für n Knoten eine -Matrix ergibt. Ein Eintrag in der i-ten Zeile und j-ten Spalte gibt hierbei an, ob eine Kante von dem i-ten zu dem j-ten Knoten führt. Steht an dieser Stelle eine 0, ist keine Kante vorhanden – eine 1 gibt an, dass eine Kante existiert, siehe Abbildung rechts. Es gibt unterschiedliche Varianten, abhängig von der Art des Graphen, z. B. für Mehrfachkanten. Die Repräsentation eines Graphen als Matrix erlaubt den Einsatz von Methoden der linearen Algebra. Die Anwendung und Untersuchung solcher Methoden bildet ein zentrales Thema in der spektralen Graphentheorie. Es bildet damit eine Schnittstelle zwischen Graphentheorie und linearer Algebra. (de)
- In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory. The adjacency matrix of a graph should be distinguished from its incidence matrix, a different matrix representation whose elements indicate whether vertex–edge pairs are incident or not, and its degree matrix, which contains information about the degree of each vertex. (en)
- Auzokidetasun-matrizea Matrize karratu bat da, erlazio bitarrak adierazteko erabiltzen dena.. (eu)
- La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias. (es)
- En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à n sommets est une matrice de dimension n × n dont l'élément non diagonal aij est le nombre d'arêtes liant le sommet i au sommet j. L'élément diagonal aii est le nombre de boucles au sommet i (pour des graphes simples, ce nombre est donc toujours égal à 0 ou 1). Cet outil mathématique est très utilisé comme structure de données en informatique (tout comme la représentation par liste d'adjacence), mais intervient aussi naturellement dans les chaînes de Markov. En particulier, la probabilité limite s'interprète comme un vecteur propre. (fr)
- 그래프 이론에서 인접 행렬(隣接行列, 영어: adjacency matrix)은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다. (ko)
- De bogenmatrix of verbindingsmatrix is een matrix die hoort bij een enkelvoudige, eindige graaf, en die aangeeft of een knoop in de graaf verbonden is met een andere knoop. De bogen in een graaf zijn de zijden die twee knopen met elkaar verbinden. Een bogenmatrix is een binaire, vierkante matrix met dimensie , waarin het aantal knopen in de graaf is. Het element in de bogenmatrix is 1 als er een boog bestaat die van naar gaat en 0 als dit niet het geval is. De bogenmatrix is een manier om een enkelvoudige, eindige graaf weer te geven. Is de bogenmatrix opgesteld, dan kan deze worden gebruikt om af te lezen hoeveel paden er van een knoop naar een andere zijn. Door de bogenmatrix tot de macht te verheffen, kan men in de -de kolom op de -de rij aflezen hoeveel paden er zijn van lengte van knoop naar knoop . Bij een ongerichte graaf is de bogenmatrix symmetrisch. In dat geval zijn de eigenwaarden van de bogenmatrix reëel en zijn de bijbehorende eigenvectoren orthogonaal. De verzamelde eigenwaarden van de matrix heet het spectrum van de graaf. De studie van grafen met hun eigenwaarden en eigenvectoren heet spectrale grafentheorie. (nl)
- グラフ理論および計算機科学において、隣接行列（りんせつぎょうれつ、英: adjacency matrix）は、有限グラフを表わすために使われる正方行列である。この行列の要素は、頂点の対がグラフ中でしているか否かを示す。 有限単純グラフの特別な例では、隣接行列はその対角上に0を持つ である。もしグラフが無向ならば、隣接行列は対称である。グラフとその隣接行列の固有値および固有ベクトルとの間の関係はスペクトラルグラフ理論において研究される。 隣接行列はグラフに関する接続行列および次数行列と区別されなければならない。接続行列は、その要素が頂点-辺の対が接続しているか否かを示す行列表現であり、次数行列は個々の頂点の次数に関する情報を含む行列表現である。 (ja)
- La matrice delle adiacenze o matrice di connessione costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi finiti. Dato un qualsiasi grafo la sua matrice delle adiacenze è costituita da una matrice binaria quadrata che ha come indici di righe e colonne i nomi dei vertici del grafo. Nel posto della matrice si trova un 1 se e solo se esiste nel grafo un arco che va dal vertice al vertice altrimenti si trova uno 0. Questi tipi di matrici sono ampiamente utilizzate nella stesura di algoritmi che operano su grafi finiti e in generale nella loro rappresentazione informatica. Nel caso la matrice di adiacenza sia una matrice sparsa, ad essa è preferibile l'impiego della lista di adiacenza. Se al posto degli 1 nella matrice si trovano dei numeri, questi sono da interpretare come il peso attribuito a ciascun collegamento. Ad esempio se l'insieme dei vertici del grafo rappresenta una serie di punti su una carta geografica, il peso degli archi può essere interpretato come la distanza dei punti che questi connettono. Se la somma degli elementi di ogni colonna è uguale a 1, allora la matrice è detta matrice di Markov, in quanto applicabile a un processo markoviano. Nel caso della rappresentazione di grafi non orientati, la matrice è simmetrica rispetto alla diagonale principale. Una delle caratteristiche fondamentali di questa matrice è di permettere di ottenere il numero di percorsi di lunghezza da un nodo ad un nodo per ottenerlo è sufficiente fare la potenza -sima della matrice e vedere il numero che compare al posto (it)
- Macierz sąsiedztwa (multi)grafu – macierz kwadratowa, w której oznacza liczbę krawędzi pomiędzy wierzchołkami i . W przypadku grafów prostych macierz sąsiedztwa jest macierzą zero-jedynkową z zerami na głównej przekątnej. Dla grafów nieskierowanych macierz sąsiedztwa jest z definicji symetryczna. Dla przykładowego grafu o sześciu wierzchołkach oraz siedmiu krawędziach: macierz sąsiedztwa jest następująca: (pl)
- Uma matriz de adjacência é uma das formas de se representar um grafo. Dado um grafo G com n vértices, podemos representá-lo em uma matriz n x n A(G)=[aij] (ou simplesmente A).A definição precisa das entradas da matriz varia de acordo com as propriedades do grafo que sedeseja representar, porém de forma geral o valor aij guarda informações sobre como osvértices vi e vj estão relacionados (isto é, informações sobre aadjacência de vi e vj). Para representar um grafo não direcionado, simples e sem pesos nas arestas, basta que as entradasaij da matriz A contenham 1 se vi e vj são adjacentes e 0 casocontrário. Se as arestas do grafo tiverem pesos, aij pode conter, ao invés de 1 quandohouver uma aresta entre vi e vj, o peso dessa mesma aresta. Por exemplo, a matriz de adjacência do grafo ao lado é Em grafos não direcionados, as matrizes de adjacência são simétricas ao longo da diagonal principal- isto é, a entrada aij é igual à entrada aji. Matrizes de adjacência de grafosdirecionados, no entanto, não são assim. Num digrafo sem pesos, a entrada aijda matriz é 1 se há um arco de vi para vj e 0 caso contrário. Um resultado interessante ocorre quando consideramos a potência k da matriz de adjacência, ou seja, o produto Antes de apresentar o resultado, vamos definir um percurso em um grafo G. Um percurso corresponde a uma sequência, finita e não vazia, de vértices do grafo, na qual (v0, v1, ..., vi, ..., vk-1, vk) é tal que, para todo 0 ≤ i ≤ k-1, vi e vi+1 são vértices adjacentes. Os vértices v0 e vk são chamados, respectivamente, de origem e fim do percurso, enquanto v1, v2, ..., vk-1 são os vértices internos ao caminho. O inteiro k é o comprimento do percurso. Um caminho em um digrafo é um percurso no qual todos os arcos estão orientados no sentido origem do percurso-fim do percurso. Se A é a matriz de adjacência de um grafo G com conjunto de vértices dado por V(G) = {v1, v2, ..., vn}, então a entrada (i,j) de Ak, com k ≥ 1, corresponde ao número de percursos (distintos) de comprimento k existentes entre os vértices vi e vj. Pode-se mostrar esse resultado por indução. Quando k = 1, o resultado segue de modo natural da definição de matriz de adjacência, uma vez que existe um percurso de comprimento 1 entre o vértice vi e o vértice vj se e só se {vi, vj} é uma aresta de G. Seja e assuma que aij (k-1) é o número de percursos distintos de comprimento k - 1 entre os vértices vi e vj em G. Considerando e como Ak = Ak-1 . A, temos que Observe que, na expressão acima, o elemento aij (k) é obtido multiplicando-se os elementos da linha i de Ak-1 pelos respectivos elementos da coluna j de A e, em seguida, efetuando-se a soma dos produtos obtidos. Todo percurso entre vi e vj de comprimento k em G consiste de um percurso entre vi e vp de comprimento k - 1, onde vp é adjacente a vj, seguido da aresta {vp, vj} e do vértice vj. O resultado decorre da hipótese de indução e da última equação. O resultado permanece válido para digrafos, fazendo-se as devidas adequações: trocando arestas por arcos e percursos por caminhos. Para ilustrar o resultado acima, observe as potências 2 e 3 da matriz de adjacência A correspondente ao grafo da figura: . O elemento (4,6) de A2 indica que não há nenhum caminho de comprimento 2 ligando os vértices 4 e 6 do grafo acima. Por outro lado, o elemento (4,6) de A3 indica que existem 3 caminhos de comprimento 3 ligando os vértices 4 e 6. São eles: (4,3,4,6), (4,5,4,6) e (4,6,4,6). (pt)
- En grannmatris eller närhetsmatris är inom matematik, specifikt grafteori, en matris som beskriver en graf genom att ange vilka noder som har bågar mellan sig. En annan sorts matriser som beskriver grafer är anslutningsmatriser. Grannmatrisen A till en (enkel) graf G med nodmängd och bågmängd E definieras som n × n-matrisen med element givna av: Med andra ord är matriselementet i kolonn i och rad j ett om det finns en båge mellan noderna och och noll annars. För en multigraf är elementen i grannmatrisen antalet bågar mellan två noder. I grannmatriser för enkla grafer är diagonalen alltid noll, något som inte gäller för multigrafers grannmatriser. För en sätts matriselementet aij vanligtvis till vikten på bågen mellan noderna i och j, om en sådan båge finns. Om det inte finns en båge sätts matriselementet till 0. I programmeringssammanhang sätts ofta oanslutna noders gemensamma matriselement till oändligheten. När anslutningsmatriser implementeras som datastrukturer används ett stort tal istället för oändligheten. Utseendet av grannmatrisen beror på hur noderna är numrerade, om man byter numrering permuteras raderna. I en oriktad graf är grannmatrisen alltid symmetrisk, eftersom en båge mellan och går åt båda håll. (sv)
- Матрица смежности — один из способов представления графа в виде матрицы. (ru)
- Матриця суміжності — один із способів представлення графу у вигляді матриці. (uk)
- 在图论和計算機科學中，邻接矩阵（英語：adjacency matrix）是一種方阵，用來表示有限图。它的每個元素代表各点之间是否有边相连。 作爲特例，簡單圖的鄰接矩陣是(0,1)矩陣並且對角線元素都爲0。無向圖的鄰接矩陣是對稱矩陣。圖和其鄰接矩陣的特徵值和特徵向量之間的關系是譜圖理論的研究對象。 圖的需要和鄰接矩陣區分。它是圖的另一種矩陣表示方式，它的元素表示各個节点-邊對是否相關。還有圖的度數矩陣，含有每個結點的度數信息。 距離矩陣可算是鄰接矩陣的擴充。 (zh)
|
| rdfs:comment
|
- في نظرية المخططات و علوم الكمبيوتر، مصفوفة المجاورة (بالإنجليزية: Adjacency Matrix) هي مصفوفة مربعة تستخدم لتمثيل . عناصر المصفوفة تعكس ما إذا كانت رؤوس الرسم البياني (vertices) متجاورة ومرتبطة أم لا. (ar)
- Una matriu d'adjacència és una matriu quadrada que s'utilitza com una forma de representar relacions binàries. (ca)
- Matice sousednosti je v matematice a informatice používaný způsob reprezentace grafu. Pro konečnou množinu vrcholů grafu G, kterých je n, má podobu čtvercové matice n×n, jejíž hodnota na místě aij je celé číslo odpovídající počtu hran vedoucích z vrcholu i do vrcholu j. Prvky na tak obvykle odpovídají počtu hran vedoucích z vrcholu i do vrcholu i (takové je běžná konvence u orientovaných grafů), ovšem někdy se na diagonálu ukládá dvojnásobek této hodnoty (taková bývá konvence u neorientovaných grafů). Pro každou třídu existuje až na prohazování řádků a sloupců právě jedna matice sousednosti a ta neodpovídá žádné jiné třídě. (cs)
- Auzokidetasun-matrizea Matrize karratu bat da, erlazio bitarrak adierazteko erabiltzen dena.. (eu)
- La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias. (es)
- 그래프 이론에서 인접 행렬(隣接行列, 영어: adjacency matrix)은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다. (ko)
- グラフ理論および計算機科学において、隣接行列（りんせつぎょうれつ、英: adjacency matrix）は、有限グラフを表わすために使われる正方行列である。この行列の要素は、頂点の対がグラフ中でしているか否かを示す。 有限単純グラフの特別な例では、隣接行列はその対角上に0を持つ である。もしグラフが無向ならば、隣接行列は対称である。グラフとその隣接行列の固有値および固有ベクトルとの間の関係はスペクトラルグラフ理論において研究される。 隣接行列はグラフに関する接続行列および次数行列と区別されなければならない。接続行列は、その要素が頂点-辺の対が接続しているか否かを示す行列表現であり、次数行列は個々の頂点の次数に関する情報を含む行列表現である。 (ja)
- Macierz sąsiedztwa (multi)grafu – macierz kwadratowa, w której oznacza liczbę krawędzi pomiędzy wierzchołkami i . W przypadku grafów prostych macierz sąsiedztwa jest macierzą zero-jedynkową z zerami na głównej przekątnej. Dla grafów nieskierowanych macierz sąsiedztwa jest z definicji symetryczna. Dla przykładowego grafu o sześciu wierzchołkach oraz siedmiu krawędziach: macierz sąsiedztwa jest następująca: (pl)
- Матрица смежности — один из способов представления графа в виде матрицы. (ru)
- Матриця суміжності — один із способів представлення графу у вигляді матриці. (uk)
- 在图论和計算機科學中，邻接矩阵（英語：adjacency matrix）是一種方阵，用來表示有限图。它的每個元素代表各点之间是否有边相连。 作爲特例，簡單圖的鄰接矩陣是(0,1)矩陣並且對角線元素都爲0。無向圖的鄰接矩陣是對稱矩陣。圖和其鄰接矩陣的特徵值和特徵向量之間的關系是譜圖理論的研究對象。 圖的需要和鄰接矩陣區分。它是圖的另一種矩陣表示方式，它的元素表示各個节点-邊對是否相關。還有圖的度數矩陣，含有每個結點的度數信息。 距離矩陣可算是鄰接矩陣的擴充。 (zh)
- In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory. (en)
- Στα μαθηματικά και στην επιστήμη υπολογιστών, ο πίνακας γειτνίασης χρησιμοποιείται για να αναπαραστήσει τις κορυφές ενός γράφου, οι οποίες συνδέονται με άλλες κορυφές. Ένας άλλος πίνακας αναπαράστασης του γράφου είναι ο πίνακας προσπτώσεων. Η σχέση μεταξύ ενός γράφου και των ιδιοτιμών και ιδιοδιανυσμάτων του πίνακα γειτνίασής του μελετάται στη φασματική θεωρία γράφων. (el)
- Eine Adjazenzmatrix (manchmal auch Nachbarschaftsmatrix) eines Graphen ist eine Matrix, die speichert, welche Knoten des Graphen durch eine Kante verbunden sind. Sie besitzt für jeden Knoten eine Zeile und eine Spalte, woraus sich für n Knoten eine -Matrix ergibt. Ein Eintrag in der i-ten Zeile und j-ten Spalte gibt hierbei an, ob eine Kante von dem i-ten zu dem j-ten Knoten führt. Steht an dieser Stelle eine 0, ist keine Kante vorhanden – eine 1 gibt an, dass eine Kante existiert, siehe Abbildung rechts. (de)
- En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à n sommets est une matrice de dimension n × n dont l'élément non diagonal aij est le nombre d'arêtes liant le sommet i au sommet j. L'élément diagonal aii est le nombre de boucles au sommet i (pour des graphes simples, ce nombre est donc toujours égal à 0 ou 1). (fr)
- La matrice delle adiacenze o matrice di connessione costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi finiti. Dato un qualsiasi grafo la sua matrice delle adiacenze è costituita da una matrice binaria quadrata che ha come indici di righe e colonne i nomi dei vertici del grafo. Nel posto della matrice si trova un 1 se e solo se esiste nel grafo un arco che va dal vertice al vertice altrimenti si trova uno 0. Nel caso della rappresentazione di grafi non orientati, la matrice è simmetrica rispetto alla diagonale principale. (it)
- Uma matriz de adjacência é uma das formas de se representar um grafo. Dado um grafo G com n vértices, podemos representá-lo em uma matriz n x n A(G)=[aij] (ou simplesmente A).A definição precisa das entradas da matriz varia de acordo com as propriedades do grafo que sedeseja representar, porém de forma geral o valor aij guarda informações sobre como osvértices vi e vj estão relacionados (isto é, informações sobre aadjacência de vi e vj). Por exemplo, a matriz de adjacência do grafo ao lado é e como Ak = Ak-1 . A, temos que . (pt)
- De bogenmatrix of verbindingsmatrix is een matrix die hoort bij een enkelvoudige, eindige graaf, en die aangeeft of een knoop in de graaf verbonden is met een andere knoop. De bogen in een graaf zijn de zijden die twee knopen met elkaar verbinden. Een bogenmatrix is een binaire, vierkante matrix met dimensie , waarin het aantal knopen in de graaf is. Het element in de bogenmatrix is 1 als er een boog bestaat die van naar gaat en 0 als dit niet het geval is. De bogenmatrix is een manier om een enkelvoudige, eindige graaf weer te geven. (nl)
- En grannmatris eller närhetsmatris är inom matematik, specifikt grafteori, en matris som beskriver en graf genom att ange vilka noder som har bågar mellan sig. En annan sorts matriser som beskriver grafer är anslutningsmatriser. Grannmatrisen A till en (enkel) graf G med nodmängd och bågmängd E definieras som n × n-matrisen med element givna av: Med andra ord är matriselementet i kolonn i och rad j ett om det finns en båge mellan noderna och och noll annars. (sv)
|