Graafide identifitseerimine: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
Väike teksti toimetamine |
täpsustatud |
||
20. rida:
== Orbiitide (positsiooniklasside) põhiomadused ==
1. Kui graafi <math>G</math> ''tipud'' <math>v_{i}, v_{j}</math> <math>\ldots</math> kuuluvad samasse positsiooni (orbiiti) <math>\Omega_{k}</math> ''siis on alamgraafid'' <math>G\setminus v_{i}</math> <math>\simeq</math> <math>G\setminus v_{j}</math> <math>\simeq</math> <math>\ldots</math> ''isomorfsed'', st omavad ühesugust [[graafi struktuur|struktuuri]].
2. Kui graafi <math>G</math> ''servad'' <math>e_{1}, e_{2}</math> <math>\ldots</math> kuuluvad samasse positsiooni (orbiiti) <math>\Omega_{n}</math> ''siis on alamgraafid'' <math>G\setminus e_{1}</math> <math>\simeq</math> <math>G\setminus e_{2}</math> <math>\simeq</math> <math>\ldots</math> ''isomorfsed'', st omavad ühesugust [[graafi struktuur|struktuuri]].
3. Kui graafi <math>G</math> ''mitteservad'' <math>ne_{1}, ne_{2}</math> <math>\ldots</math> <math>\ldots</math> kuuluvad samasse positsiooni (orbiiti) <math>\Omega_{n}</math> ''siis on ülemgraafid'' <math>G\cup e_{1}</math> <math>\simeq</math> <math>G\cup e_{2}</math> <math>\simeq</math> <math>\ldots</math> ''isomorfsed'', st omavad ühesugust [[graafi struktuur|struktuuri]].
4. Tipupaari-orbiitide <math>\Omega_{n}</math> baasil saadud isomorfsed alamgraafid kujutavad endast graafi <math>G</math> ''naaber alamstruktuuri'' ja/või ''naaber ülemstruktuuri'', mida üldistatult lihtsalt ''''naaberstruktuuriks'''' <math>G^{adj}</math> nimetame.
63. rida:
Rühmateoreetilisest aspektist on graafi struktuuri ja sümmeetriaomadusi teadaolevalt varem uurinud tipuorbiitide tasemel vaid B. Weisfeiler <ref> B. Weisfeiler. '' On Construction and Identification of Graphs''. Springer Lect. Notes Math., 558, 1976 </ref>.
Oluline on, et ''rühmateoreetilise ja maatriksastme lähenemiste teel saadud tulemused langevad kokku''. Selline [[graafide identifitseerimine|graafide identifitseerimise]] viis viib [[isomorfismiprobleem]]i ja [[Ulami hüpotees]]i selgitamiseni ning on seotud [[graafide süsteem]]ide moodustamisega.
== Vaata ka ==
| |||