153 research outputs found
K-geodominating sets in graphs and related concepts
No full textMnožica vozlišč S grafa Г je geodominantna množica, če poljubno vozlišče grafa Г leži na vsaj enem intervalu med vozliščema iz S. Za naravno število k je vozlišče v k-geodominirano z vozliščema x,y∈V(Г), če v leži na neki najkrajši poti dolžine k med vozliščema x in y. Podmnožica S⊆V(Г) je k-geodominantna množica, če je vsako vozlišče v∈V(Г) S k-geodominirano z nekim parom vozlišč iz S. Množica vozlišč v grafu je neodvisna, če nobeni dve vozlišči iz te množice nista povezani. Neodvisna množica, ki je (k"-" )geodominantna, se imenuje neodvisna (k"-" )geodominantna množica grafa Г. Dominantna množica grafa Г je taka podmnožica D⊆V(Г), da je vsako vozlišče, ki ni v D, sosedno z vsaj enim vozliščem iz D.
Diplomsko delo obravnava zveze med geodominantnimi, k-geodominantnimi, dominantnimi in neodvisnimi množicami v poljubnih grafih. Podane so nekatere lastnosti geodominantnih množic v povezavnih grafih in kartezičnih produktih. Prav tako so obravnavane lastnosti neodvisnih geodominantnih in neodvisnih k-geodominantnih množic.A set S of vertices of a graph Г is a geodominating set if every vertex of Г lies in at least one interval between the vertices of S. For an integer k≥1, a vertex v is k-geodominated by a pair x,y∈V(Г) if v lies on a shortest path of length k between vertices x and y. A subset S⊆V(Г) is a k-geodominating set if each vertex v∈V(Г) S is k-geodominated by some pair of vertices of S. An independent set is a set of vertices in a graph, no two of which are adjacent. An independent set of in Г that is a (k-)geodominating set of Г is called an independent (k-)geodominating set of Г. A dominating set for a graph Г is a subset D⊆V(Г) such that every vertex not in D is adjacent to at least one member of D.
The graduation thesis investigates relationships between geodominating, k-geodominating sets, dominating sets and independent sets in arbitrary graphs. Some properties of geodominating sets in line graphs and Cartesian products are given. Also, independent geodominating sets and independent k-geodominating sets are studied
Perepiska i bumagi grafa Borisa Petrovicha Sheremeteva. 1704-1722 gg.
No full text"Pechatano po raspori͡azhenīi͡u sovi͡eta Imperatorskago russkago istoricheskago obshchestva, pod nabli͡udeniem chlena obshchestva grafa S.D. Sheremeteva."Mode of access: Internet.With bookplate of Biblioteka N. K. Siniagina
Aproksimativni algoritmi za generisanje k-NN grafa
No full textNearest neighbor graphs are modeling proximity relationships between objects. They are widely used in many areas, primarily in machine learning, but also in information retrieval, biology, computer graphics,geographic information systems, etc. The focus of this thesis are knearest neighbor graphs (k-NNG), a special class of nearest neighbor graphs. Each node of k-NNG is connected with directed edges to its k nearest neighbors.A brute-force method for constructing k-NNG entails O(n 2 ) distance calculations. This thesis addresses the problem of more efficient k-NNG construction, achieved by approximation algorithms. The main challenge of an approximation algorithm for k-NNG construction is to decrease the number of distance calculations, while maximizing the approximation’s accuracy.NN-Descent is one such approximation algorithm for k-NNG construction, which reports excellent results in many cases. However, it does not perform well on high-dimensional data. The first part of this thesis summarizes the problem, and gives explanations for such a behavior. The second part introduces five new NN-Descent variants that aim to improve NN-Descent on high-dimensional data. The performance of the proposed algorithms is evaluated with an experimental analysis.Finally, the third part of this thesis is dedicated to k-NNG update algorithms. Namely, in the real world scenarios data often change over time. If data change after k-NNG construction, the graph needs to be updated accordingly. Therefore, in this part of the thesis, two approximation algorithms for k-NNG updates are proposed. They are validated with extensive experiments on time series data.Graf najbližih suseda modeluje veze između objekata koji su međusobno bliski. Ovi grafovi se koriste u mnogim disciplinama, pre svega u mašinskom učenju, a potom i u pretraživanju informacija, biologiji, računarskoj grafici, geografskim informacionim sistemima, itd. Fokus ove teze je graf k najbližih suseda (k-NN graf), koji predstavlja posebnu klasu grafova najbližih suseda. Svaki čvor k-NN grafa je povezan usmerenim granama sa njegovih k najbližih suseda.Metod grube sile za generisanje k-NN grafova podrazumeva O(n 2 ) računanja razdaljina između dve tačke. Ova teza se bavi problemom efikasnijeg generisanja k-NN grafova, korišćenjem aproksimativnih algoritama.Glavni cilj aprokismativnih algoritama za generisanje k-NN grafova jeste smanjivanje ukupnog broja računanja razdaljina između dve tačke, uz održavanje visoke tačnosti krajnje aproksimacije.NN-Descent je jedan takav aproksimativni algoritam za generisanje k-NN grafova. Iako se pokazao kao veoma dobar u većini slučajeva, ovaj algoritam ne daje dobre rezultate nad visokodimenzionalnim podacima. Unutar prvog dela teze, detaljno je opisana suština problema i objašnjeni su razlozi za njegovo nastajaneU drugom delu predstavljeno je pet različitih modifikacija NN-Descent algoritma, koje za cilj imaju njegovo poboljšavanje pri radu nad visokodimenzionalnim podacima. Evaluacija ovih algoritama je data kroz eksperimentalnu analizu.Treći deo teze se bavi algoritmima za ažuriranje k-NN grafova. Naime,podaci se vrlo često menjaju vremenom. Ukoliko se izmene podaci nad kojima je prethodno generisan k-NN graf, potrebno je graf ažurirati u skladu sa izmenama. U okviru ovog dela teze predložena su dva aproksimativna algoritma za ažuriranje k-NN grafova. Ovi algoritmi su evaluirani opširnim eksperimentima nad vremenskim serijama
Aproksimativni algoritmi za generisanje k-NN grafa
No full textNearest neighbor graphs are modeling proximity relationships between objects. They are widely used in many areas, primarily in machine learning, but also in information retrieval, biology, computer graphics,geographic information systems, etc. The focus of this thesis are knearest neighbor graphs (k-NNG), a special class of nearest neighbor graphs. Each node of k-NNG is connected with directed edges to its k nearest neighbors.A brute-force method for constructing k-NNG entails O(n 2 ) distance calculations. This thesis addresses the problem of more efficient k-NNG construction, achieved by approximation algorithms. The main challenge of an approximation algorithm for k-NNG construction is to decrease the number of distance calculations, while maximizing the approximation’s accuracy.NN-Descent is one such approximation algorithm for k-NNG construction, which reports excellent results in many cases. However, it does not perform well on high-dimensional data. The first part of this thesis summarizes the problem, and gives explanations for such a behavior. The second part introduces five new NN-Descent variants that aim to improve NN-Descent on high-dimensional data. The performance of the proposed algorithms is evaluated with an experimental analysis.Finally, the third part of this thesis is dedicated to k-NNG update algorithms. Namely, in the real world scenarios data often change over time. If data change after k-NNG construction, the graph needs to be updated accordingly. Therefore, in this part of the thesis, two approximation algorithms for k-NNG updates are proposed. They are validated with extensive experiments on time series data.Graf najbližih suseda modeluje veze između objekata koji su međusobno bliski. Ovi grafovi se koriste u mnogim disciplinama, pre svega u mašinskom učenju, a potom i u pretraživanju informacija, biologiji, računarskoj grafici, geografskim informacionim sistemima, itd. Fokus ove teze je graf k najbližih suseda (k-NN graf), koji predstavlja posebnu klasu grafova najbližih suseda. Svaki čvor k-NN grafa je povezan usmerenim granama sa njegovih k najbližih suseda.Metod grube sile za generisanje k-NN grafova podrazumeva O(n 2 ) računanja razdaljina između dve tačke. Ova teza se bavi problemom efikasnijeg generisanja k-NN grafova, korišćenjem aproksimativnih algoritama.Glavni cilj aprokismativnih algoritama za generisanje k-NN grafova jeste smanjivanje ukupnog broja računanja razdaljina između dve tačke, uz održavanje visoke tačnosti krajnje aproksimacije.NN-Descent je jedan takav aproksimativni algoritam za generisanje k-NN grafova. Iako se pokazao kao veoma dobar u većini slučajeva, ovaj algoritam ne daje dobre rezultate nad visokodimenzionalnim podacima. Unutar prvog dela teze, detaljno je opisana suština problema i objašnjeni su razlozi za njegovo nastajaneU drugom delu predstavljeno je pet različitih modifikacija NN-Descent algoritma, koje za cilj imaju njegovo poboljšavanje pri radu nad visokodimenzionalnim podacima. Evaluacija ovih algoritama je data kroz eksperimentalnu analizu.Treći deo teze se bavi algoritmima za ažuriranje k-NN grafova. Naime,podaci se vrlo često menjaju vremenom. Ukoliko se izmene podaci nad kojima je prethodno generisan k-NN graf, potrebno je graf ažurirati u skladu sa izmenama. U okviru ovog dela teze predložena su dva aproksimativna algoritma za ažuriranje k-NN grafova. Ovi algoritmi su evaluirani opširnim eksperimentima nad vremenskim serijama
K-connected Graph Generation
No full textDarbs ir veltīts k-sakarīgu grafu ģenerēšanas jautājumam. Darbā tiek piedāvāti četri algoritmi grafu ģenerēšanai: atkārtota grafu ģenerēšana pēc Erdeša-Renji modeļa ar mērķi iegūt k-sakarīgu grafu; 2-sakarīga grafa izveidošana ar ceļu pievienošanu; 3-sakarīga grafa veidošana ar virsotņu stiepšanu; k-sakarīga grafa veidošana, pievienojot jaunas virsotnes un savienojot tās ar visām vai dažām no esošām virsotnēm. Algoritmi tiek izpētīti un salīdzināti. Kā izrādās, 2- un 3-sakarīgu grafu ģenerēšanas algoritmi spēj ģenerēt grafus ar varbūtību sadalījumu, līdzīgu pirmajam algoritmam, taču ievērojami ātrāk. Pēdējam algoritmam grafu sadalījums nav vienmērīgs, taču to var pielietot, ja nepieciešams ātri uzģenerēt patvaļīga sakarīguma un izmēra grafu.In this work, the author seeks to solve the problem of generating k-connected graphs. Four algorithms are described: repeated graph generation using Erdős–Rényi random graph model with a goal of producing a k-connected graph; construction of 2-connected graphs by adding paths; construction of 3-connected graphs by stretching vertices; construction of k-connected graphs by adding new vertices and connecting them to some or all of the existing ones. Algorithms are compared. It appears that algorithms for generating 2- and 3-connected graphs have graph probability distributions which are similar to that of the first algorithm but they operate considerably faster. The latter algorithm does not have an equal graph probability distribution but permits generating graphs of any size and connectivity
The locating-chromatic number of a graph
No full textV diplomskem delu je obravnavano locirajoče kromatično število grafa. Za barvanje povezanega grafa naj bo urejena particija množice vozlišč glede na barvanje . Za vozlišče grafa je barvna koda vozlišča urejena -terica , kjer je , za . Če imata različni vozlišči različni barvni kodi, potem imenujemo locirajoče barvanje. Locirajoče kromatično število, , je najmanjše število barv, potrebnih za locirajoče barvanje grafa . Meje za locirajoče kromatično število povezanega grafa so ugotovljene s stališča njegovega reda in premera. Določeni so vsi povezani grafi reda z locirajočim kromatičnim številom . Pokazano je, da za vsak par naravnih števil obstaja povezan graf s kromatičnim številom in locirajočim kromatičnim številom . Določeno je locirajoče kromatično število nekaterih znanih grafov. Posebej je predstavljeno locirajoče kromatično število dreves.In this graduation thesis locating-chromatic number of a graph will be discussed. For a coloring of a connected graph , let be an ordered partition of with respect to the coloring . For a vertex of , the color code of is the ordered -tuple , where for . If distinct vertices have distinct color codes, then is called a locating-coloring. The locating-chromatic number is the minimum number of colors in a locating-coloring of . Bounds for the locating-chromatic number of a connected graph are established in terms of its order and diameter. All connected graphs of order with locating-chromatic number are determined. It is shown that for each pair of integers with there exists a connected graph with chromatic number and locating-chromatic number . The locating-chromatic number of some well-known graph classes is determined, and the locating-chromatic number of trees is studied
Zhurnal reli͡at͡sīĭ k ei͡a imperatorskomu velichestvu Kaluzhskago, Tulʹskago i Ri͡azanskago general-gubernatora Mikhaĭla Nikiticha Krechetnikova, v 1782-1787 godakh /
No full textContains also Chernyshov, Z.G. Pisʹma k generalu i kavaleru Mikhaĭlu Nikitichu Krechetnikovu grafa Zakhara Grigorʹevicha Chernyshova i drugikh s 1769 po 1785 g."Iz IV-ĭ knigi Chtenīĭ v Imp. Obshchestvi͡e istorīi i drevnosteĭ rossīĭskikh pri Moskovskom universiteti͡e 1863"--Verso of t.p.Mode of access: Internet
Katalog galerei grafa N.A. Kusheleva-Bezborodko /
No full textAt head of title: Kartinnai︠a︡ galerei︠a︡ Imperatorskoĭ akademīi khudozhestvMode of access: Internet
Graph energy
No full textMagistrsko delo zajema področje kemijske teorije grafov. Energija grafa je ena izmed invariant grafa, ki je povezana s fizikalno-kemijskimi lastnostmi obravnavanih molekul. Energijo grafa definiramo kot vsoto absolutnih vrednosti vseh lastnih vrednosti matrike sosednosti poljubnega grafa. V magistrskem delu si bomo ogledali kako izračunamo energijo poljubnega grafa, njegove spodnje in zgornje meje ter metode dokazovanja za primerjavo energij različnih družin grafov med seboj. Definirali bomo tudi molekulske grafa, ki so za nas pomembni, saj tako povežemo kemijske molekule z njimi pripadajočimi molekulskimi grafi, za katere lahko izračunamo energijo grafa z matematičnim pristopom.
V prvem delu je navedenih nekaj pomembnih definicij in izrekov iz področja teorije grafov in linearne algebre, ki jih potrebujemo v nadaljevanju. V drugem delu definiramo energijo grafa in spekter grafa. V tretjem delu sta opisani Hücklova molekularna orbitalna teorija in Coulsonova integralna formula. V četrtem delu navedemo sedem metod dokazovanja za izračun energije grafa, v petem delu pa navedemo spodnje in zgornje meje za nekatere družine grafov. V zadnjem delu je navedena kemijska teorija grafov in definicije molekulskih grafov.The master thesis examines the field of chemical graph theory. Graph energy is one of the graph invariants, which is associated to the physicochemical properties of the selected molecules. Graph energy is defined as the sum of the absolute values of all the eigenvalues of the adjacency matrix of the arbitrary graph. In the master thesis, we introduce formulas for calculating graph energy for the arbitrary graph, its lower and upper bounds, and a variety of methods for comparing the energies of different families of graphs. We define the molecular graphs that are important for uschemical molecules are related to the corresponding molecular graphs, for which we can calculate the graph energy with a mathematical approach.
The first part contains definitions and important theorems from Graph Theory and Linear Algebra. In the second part, we define graph energy and the graph spectrum. In the third chapter, we introduce the Hückel molecular orbital theory and Coulson integral formula. In the fourth chapter, we present seven proof methods for calculating the graph energy. In the next chapter, we specify lower and upper bounds for the selected graph families. Chemical graph theory and definitions of molecular graphs are explained in the last chapter
PLANARITY OF GRAPHS
No full textV diplomskem delu predstavimo merjenja ravninskosti grafov. Graf G je ravninski, če ga lahko narišemo v ravnini tako, da noben par povezav nima skupnega vozlišča, razen v vozlišču, ki je njuno skupno krajišče. Obravnavamo načine za določanje ravninskosti s pomočjo metode iskanja podgrafa, ki je subdivizija od K5 ali K3,3, določanja prekrižnega števila, debeline grafov in delitvenega števila pri določenih grafov. Grafa K5 in K3,3 nista ravninska grafa, torej če G vsebuje podgraf, ki je subdivizija od K5 ali K3,3, potem G ni ravninski. Debelina grafa G, t(G), je minimalno število ravninskih grafov iz katerih lahko sestavimo graf G. Torej t(G)=k pomeni, da je enak G=H1UH2U,...,Hk, kjer je Hi ravninski za vsaki i in graf G ne moremo razstaviti v k-1 ravninskih grafov. Na koncu diplomske naloge še predstavimo Heawood-ov problem dežel. Heawood je dokazal, da je vsak zemljevid 2-dežel lahko pobarvan z 12 barvami in obstaja zemljevid 2-dežel, ki potrebuje 12 barv.In this diploma work we introduce planarity of graphs. Graph G is planar, if we can draw it in the plain so that no pair of edges intersect in the same vertex, except in theirs endvertices. We check the planarity of a graph with the examination of its subgraph. If the graph G has a subgraph, that is a subdivision of K5 or K3,3 then G is not planar. If a graph is not planar, we are interested in its crossing number, thicknesses and splitting number. The tickness of a graph G, denoted by t(G), is the minimum number of planar subgraphs in a decomposition of G into planar subgraphs. So t(G)=k means there is a decomposition of G= H1UH2U,...,Hk, where Hi is planar for each i and there is no decomposition of G into k-1 planar subgraphs. At the end of the diploma we introduce Heawood\u27s empire problem . Heawood prove, that every 2-pire map can be colored by twelve colors and there exist a 3-pire map that require twelve colors
- …
