Vikipedio:Projekto matematiko/Najbarmatrico

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al Najbarmatrico (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En matematiko kaj komputiko, la najbarmatrico por finia (grafikaĵo, grafeo) G sur n verticoj estas n × n matrico kie la _nondiagonal_ (termo, koeficiento, elemento) a_{_ij_} estas la nombro de randoj (aniĝanta, aliganta, aliĝanta) vertico i kaj vertico j, kaj la diagonalo (termo, koeficiento, elemento) a_ii estas ĉu dufoje la nombro de cikloj je vertico i aŭ (justa, ĵus) la nombro de cikloj ((uzadoj, uzadas) diferenci; ĉi tiu artikolo sekvas la antaŭa; orientitaj grafeoj ĉiam sekvi la lasta). Tie ekzistas unika najbarmatrico por ĉiu (grafikaĵo, grafeo), kaj ĝi estas ne la najbarmatrico de (ĉiu, iu) alia (grafikaĵo, grafeo). En la speciala okazo de finia, simpla grafeo, la najbarmatrico estas (0,1)-matrico kun nuloj sur ĝia diagonalo. Se la (grafikaĵo, grafeo) estas nedirektita, la najbarmatrico estas simetria.

Por _sparse_ (grafikaĵoj, grafeoj), tio estas (grafikaĵoj, grafeoj) kun kelkaj randoj, _adjacency_ listo estas ofte la (preferis, pliamita) prezento ĉar ĝi uzas malpli spaco. Alternativa matrica prezento por (grafikaĵo, grafeo) estas la incidmatrico.

La interrilato inter (grafikaĵo, grafeo) kaj ĝia najbarmatrico estas studita en spektra grafeteorio.

Enhavo 1 (Ekzemploj, Ekzemplas) 2 Propraĵoj 3 Variadoj 4 Komerco-_offs_ kiel datumstrukturo 5 Referencoj

[redaktu] (Ekzemploj, Ekzemplas)

La najbarmatrico por jena vertica markita grafeo

estas

[redaktu] Propraĵoj

La najbarmatrico de sendirekta grafeo estas simetria, kaj pro tio havas plenumi aro de (ajgenoj, ajgenas) kaj perpendikulara ajgenvektora bazo. La aro de (ajgenoj, ajgenas) de (grafikaĵo, grafeo) estas la spektro de la (grafikaĵo, grafeo).

Supozi du direktita aŭ sendirektaj grafeoj G₁ kaj G₂ kun _adjacency_ matricoj A₁ kaj A₂ estas donita. G₁ kaj G₂ estas izomorfia se kaj nur se tie ekzistas permuta matrico P tia (tiu, ke, kiu)

_PA_₁P ⁻¹ = A₂.

En aparta, A₁ kaj A₂ estas simila kaj havi pro tio la sama minimuma polinomo, karakteriza polinomo, (ajgenoj, ajgenas), determinanto kaj spuro. Ĉi tiuj povas pro tio servi kiel izomorfio (invariantoj, invariantas) de (grafikaĵoj, grafeoj). Donita la du _adjacency_ matricoj, ĝi estas ebla al rekonstrui la permuta matrico uzita: vidi permuta matrico por (detaloj, detalas).

(Tononomo, Noto, Noti), tamen, (tiu, ke, kiu) la konversacii estas ne vera: du (grafikaĵoj, grafeoj) (majo, povas) posedi la sama aro de (ajgenoj, ajgenas) sed ne esti izomorfia (unu ne povas 'aŭdi' la formo de (grafikaĵo, grafeo)). La multipliko kun la permuta matrico povas esti bildigita kiel _relabeling_ de la verticoj.

Se A estas la najbarmatrico de la direktita aŭ sendirekta grafeo G, tiam la matrico Aⁿ (kio estas la matrica multipliko de n (kopioj, kopias) de A) havas (interezanta, interesanta) interpretado: la (termo, koeficiento, elemento) en (linio, vico) mi kaj kolumno j donas la nombro de (direktita aŭ nedirektita) vojoj de longo n de vertico mi al vertico j.

La matrico Mi − A (kie Mi signifas la n-per-n identa matrico) estas inversigebla se kaj nur se estas ne direktita (cikloj, ciklas) en la (grafikaĵo, grafeo) G. En ĉi tiu (kesto, okazo), la inverso (Mi − A)⁻¹ havas jena interpretado: la (termo, koeficiento, elemento) en (linio, vico) mi kaj kolumno j donas la nombro de direktitaj vojoj de vertico mi al vertico j (kiu estas ĉiam finia se estas ne direktita (cikloj, ciklas)). Ĉi tiu povas esti komprenita uzanta la geometria serio por matricoj:

(Mi − A)⁻¹ = Mi + A + A² + A³ + ...

(korespondanta, respektiva) al la fakto (tiu, ke, kiu) la nombro de vojoj de mi al j egalas la nombro de vojoj de longo 0 plus la nombro de vojoj de longo 1 plus la nombro de vojoj de longo 2 kaj tiel plu La ĉefa diagonalo de ĉiu najbarmatrico (korespondanta, respektiva) al (grafikaĵo, grafeo) sen cikloj havas ĉiuj nulaj elementoj.

[redaktu] Variadoj

La (0,−1,1)-najbarmatrico de simpla grafeo havas nulo sur la diagonalo kaj (termo, koeficiento, elemento) a_{_ij_} = −1 se _ij_ estas rando kaj 1 se ĝi estas ne. Ĉi tiu matrico estas uzita en studanta forte regulaj grafeoj kaj (du-grafeoj, du-grafeas).

[redaktu] Komerco-_offs_ kiel datumstrukturo

Kiam uzita kiel datumstrukturo, la ĉefa _competitor_ por la najbarmatrico estas la _adjacency_ listo. Ĉar ĉiu (termo, koeficiento, elemento) en la najbarmatrico postulas nur unu malmulto, ili povas esti (prezentita, prezentis) en tre kompakta vojo, okupanta nur n²/8 (bitokoj, bitokas, bajtoj, bajtas) de _contiguous_ spaco, kie n estas la nombro de verticoj. Ekster (justa, ĵus) evitanta (rubis, malŝparita, disipita, elĵetaĵita, forĵet(ind)aĵis) spaco, ĉi tiu kompakteco kuraĝigas lokeco de referenco.

Aliflanke, por _sparse_ (grafikaĵo, grafeo), _adjacency_ (listoj, listas) konkeri ekster, ĉar ili ne uzi (ĉiu, iu) spaco al prezenti randoj kiu estas ne (prezenti, aktuala). Uzanta naiva ligillista realigo sur 32-malmulta komputilo, _adjacency_ listo por sendirekta grafeo postulas pri 16e (bitokoj, bitokas, bajtoj, bajtas) de memoro, kie e estas la nombro de randoj.

Notanta (tiu, ke, kiu) simpla grafeo povas havi maksimume n² randoj, permesantaj cikloj, ni povas estu d = e/n² signifi la denseco de la (grafikaĵo, grafeo). Tiam, 16e > n²/8, aŭ la _adjacency_ lista prezento okupas pli spaco, precize kiam d > 1/128. Tial (grafikaĵo, grafeo) devas esti _sparse_ ja al pravigi _adjacency_ lista prezento.

Ekster la spaco _tradeoff_, la malsamaj datumstrukturoj ankaŭ faciligi malsama (operacioj, operacias). Trovantaj ĉiuj verticoj najbara al donita vertico en _adjacency_ listo estas kiel simpla kiel leganta la listo. Kun najbarmatrico, tuta (linio, vico) devas anstataŭe esti (skanadita, skanita, skandita), kiu prenas O(n) tempo. Ĉu estas rando inter du donitaj verticoj povas esti difinita senprokraste kun najbarmatrico, dum postulanta tempo proporcie kun la minimuma grado de la du verticoj kun la _adjacency_ listo.

[redaktu] Referencoj

• Tomaso H. Cormen-a, Karlo E. _Leiserson_, _Ronald_ L. _Rivest_, kaj _Clifford_ Stein-a. Enkonduko al (Algoritmoj, Algoritmas), (Sekundo, Dua) Redakcio. _MIT_ Premi kaj _McGraw_-Monteto, 2001. ISBN 0262032937. Sekcio 22.1: Prezentoj de (grafikaĵoj, grafeoj), _pp_.527–531.