Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жазықтықтағы бірлік дискілердің қиылысу графы
Intersection graph of unit disks in the plane
Геометриялық графтар теориясында бірлік дискі граф – Евклид жазықтығындағы бірлік дискілер жиынының қиылысу графы. Яғни, бұл графта әр дискіге бір төбе сәйкес келеді және егер сәйкес дискілердің орталары бірлік қашықтықта болса, онда екі төбе арасында қабырға болады. Олар көбінесе Пуассон нүктелік процесінен құралады, бұл оларды кездейсоқ құрылымның қарапайым мысалы етеді.
In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corresponding vertices lie within a unit distance of each other. They are commonly formed from a Poisson point process, making them a simple example of a random structure.
Қасиеттері
Бірлік дискі графигінің кез келген индукцияланған кішіграфигі де бірлік дискі графигі болып табылады. Бірлік дискі графигі емес графтың мысалы – алты жапыраққа жалғанған бір орталық түйіні бар жұлдыз: егер алты бірлік дискінің әрқайсысы ортақ бірлік дискіге жанасса, онда осы алты дискінің екеуі бір-біріне жанасуы керек. Сондықтан, бірлік дискі графиктері индукцияланған кішіграфиктерді қамти алмайды. Басқа да көптеген тыйым салынған индукцияланған кішіграфиктер белгілі. Белгіленген төбелері бар бірлік дискі графиктерінің саны экспоненциалдық фактор ішінде орналасқан. Бұл жылдам өсім бірлік дискі графиктерінің шектеулі егіз ені болмайды дегенді көрсетеді.
Every induced subgraph of a unit disk graph is also a unit disk graph. An example of a graph that is not a unit disk graph is the star with one central node connected to six leaves: if each of six unit disks touches a common unit disk, some two of the six disks must touch each other. Therefore, unit disk graphs cannot contain an induced subgraph. Infinitely many other forbidden induced subgraphs are known. The number of unit disk graphs on labeled vertices is within an exponential factor of This rapid growth implies that unit disk graphs do not have bounded twin width.
Қолданбалар
, бірлік дискі графикалары компьютерлік ғылымда арнайы сымсыз байланыс желілерінің топологиясын модельдеу үшін қолданылып келеді. Бұл қолданбада түйіндер базалық станциясыз тікелей сымсыз байланыс арқылы қосылады. Барлық түйіндер біртекті және барлық бағыттағы антенналармен жабдықталған деп есептеледі. Түйіндердің орналасуы Евклидтік нүктелер ретінде модеделденеді, ал бір түйінден екінші түйінді сигнал қабылдай алатын аймақ шеңбер ретінде модеделденеді. Егер барлық түйіндерде бірдей қуаттылықтағы хабар тарату құралдары болса, онда бұл шеңберлердің бәрі бірдей болады. Кездейсоқ түрде жасалған диск орталықтарынан құралған бірлік дискі графикалары түріндегі кездейсоқ геометриялық графиктер де перколяция және басқа да әртүрлі құбылыстардың моделі ретінде пайдаланылды.
Beginning with the work of , unit disk graphs have been used in computer science to model the topology of ad hoc wireless communication networks. In this application, nodes are connected through a direct wireless connection without a base station. It is assumed that all nodes are homogeneous and equipped with omnidirectional antennas. Node locations are modelled as Euclidean points, and the area within which a signal from one node can be received by another node is modelled as a circle. If all nodes have transmitters of equal power, these circles are all equal. Random geometric graphs, formed as unit disk graphs with randomly generated disk centres, have also been used as a model of percolation and various other phenomena.
Есептеу күрделілігі
Егер бір адамға кез келген белгіленген өлшемдегі кеңістікте бірлік дискілердің (немесе олардың орталықтарының) жиынтығы берілсе, орталықтарды жақын маңдағы бүтін сандық тор нүктелеріне дөңгелектеу арқылы, бір-бірінен тұрақты қашықтықтағы барлық орталықтарды табу үшін хэш-кестесін пайдалану арқылы және шеңберлері қиылысатын жұптар үшін алынған жұптар тізімін сүзгілеу арқылы сәйкес бірлік дискілер графигін сызықтық уақытта құруға болады. Бұл алгоритм қарастырған жұптар санының соңғы графиктегі қабырғалар санына қатынасы тұрақты, бұл сызықтық уақытпен байланысты. Алайда, бұл тұрақты өлшемнің функциясы ретінде экспоненциалды түрде өседі. Геометриясыз берілген графикті бірлік дискілер графигі ретінде бейнелеуге болатынын анықтау NP қиын (нақтырақ айтқанда, нақты сандардың экзистенциалдық теориясы үшін толық). Сонымен қатар, бірлік дискілер графигінің нақты координаттарын шығару полиномиалдық уақытта мүмкін емес: мұндай бейнелеуде экспоненциалды түрде көптеген биттерді қажет ететін бірлік дискілер графиктері бар. Дегенмен, көптеген маңызды және қиын графиктарды оңтайландыру мәселелері, мысалы, ең үлкен тәуелсіз жиын, графиктерді бояу және ең аз доминантты жиын, осы графиктердің геометриялық құрылымын пайдалану арқылы тиімді түрде жуықтауға болады, ал ең үлкен клика мәселесі осы графиктер үшін дәл осы уақытқа дейін шешіледі. Дискілік бейнелеуі белгісіз болса да, және кіріс ретінде абстрактты график берілген болса да, полиномиалдық уақытта максималды кликаны немесе графиктің бірлік дискілер графигі емес екендігінің дәлелін шығару және ашкөз бояу алгоритмін қолдану арқылы оңтайлы бояуды 3 есеге жуықтау мүмкін.
If one is given a collection of unit disks (or their centres) in a space of any fixed dimension, it is possible to construct the corresponding unit disk graph in linear time, by rounding the centres to nearby integer grid points, using a hash table to find all pairs of centres within constant distance of each other, and filtering the resulting list of pairs for the ones whose circles intersect. The ratio of the number of pairs considered by this algorithm to the number of edges in the eventual graph is a constant, giving the linear time bound. However, this constant grows exponentially as a function of the dimension. It is NP hard (more specifically, complete for the existential theory of the reals) to determine whether a graph, given without geometry, can be represented as a unit disk graph. Additionally, it is impossible in polynomial time to output explicit coordinates of a unit disk graph representation: there exist unit disk graphs that require exponentially many bits of precision in any such representation. However, many important and difficult graph optimization problems such as maximum independent set, graph coloring, and minimum dominating set can be approximated efficiently by using the geometric structure of these graphs, and the maximum clique problem can be solved exactly for these graphs in polynomial time, given a disk representation. Even if a disk representation is not known, and an abstract graph is given as input, it is possible in polynomial time to produce either a maximum clique or a proof that the graph is not a unit disk graph, and to 3 approximate the optimum coloring by using a greedy coloring algorithm.