Search

Glavna svrha ovog rada je pokazati na koji način su povezana područja linearne algebre i teorije grafova te kako njihovu vezu možemo iskoristiti za rješavanje problema u stvarnom životu. U prvom poglavlju navodimo definicije, teoreme i rezultate iz linearne algebre i teorije grafova koji su nužni za shvaćanje glavnog dijela rada. Drugo, treće i četvrto poglavlje bavi se proučavanjem matrice susjedstva, matrice incidencije i Laplaceove matrice. Definiramo svaku od navedenih matrica, na stvarnim primjerima prikazujemo načine njihovog određivanja te prezentiramo njihove primjene u proučavanju pripadnih grafova. U petom i šestom poglavlju promatramo matricu udaljenosti stabla i matricu otpora. Definiramo navedene matrice i proučavamo njihova svojstva i primjene. Poseban naglasak je dan na rezultate vezane uz njihove svojstvene vrijednosti, determinante i povezanosti s Laplaceovom matricom. The main purpose of this thesis is to show the connections between linear algebra and graph theory and their applications to solving real life problems. In the first chapter we give basic definitions, theorems and results from linear algebra and graph theory which are vital for further understanding of the thesis. In chapters two, three and four we are focused on adjacency and incidence matrices along with the Laplacian matrix. We define each of these matrices, we show how to determine them by using real life examples and we present their applications to the study of the underlying graphs. In the last two chapters, chapters five and six, we examine the distance matrix of a tree and the resistance matrix. We introduce the aforementioned matrices and study their properties and applications. Special emphasis is given to the results concerning their eigenvalues, determinants and connections with the Laplacian matrix.

Graf je struktura defirnirana konačnim skupom vrhova i skupom bridova. Neka svojstva grafa usko su vezana uz njegov spektar, skup svojstvenih vrijednosti matrice susjedstva grafa. U ovom je radu dan pregled osnovnih rezultata o svojstvenim vrijednostima grafa i njihovim primjenama. Najviše svojstava grafa vezano je s najvećom, drugom po redu najvećom i najmanjom svojstvenom vrijednosti, te brojem različitih svojstvenih vrijednosti grafa. Na primjer, najveća svojstvena vrijednost se smanjuje uklanjanjem vrhova ili bridova iz grafa, dok druga po redu najveća svojstvena vrijednost daje informacije o algebarskoj povezanosti grafa, a grafovi s malim brojem svojstvenih vrijednosti često imaju svojstvo simetričnosti. Problemi razmotreni u ovom radu koji iziskuju modeliranje pomoću grafova su klasteriranje, odnosno grupiranje podataka u svrhu podjele prema nekom kriteriju sličnosti, raspoznavanje uzoraka koje je usko povezano s klasteriranjem i modeliranje kompleksnih mreža, čija primjena je česta u mrežnom prometu. Konačno, izrađena je interaktivna aplikacija za računanje spektra grafa. A graph is a structure defined by a finite set of vertices and a set of edges. Some graph properties are closely related to its spectrum, a set of eigenvalues of the adjacency matrix. This thesis provides an overview of the basic results on the eigenvalues of graphs and their applications. Most graph properties are related to the largest, second largest and smallest eigenvalues, and the number of different eigenvalues of the graph. For example, the largest eigenvalue is reduced by removing vertices or edges from the graph, while the second largest eigenvalue provides information about the algebraic connectivity of the graph, and graphs with a small number of eigenvalues often have the property of symmetry. Problems discussed in this thesis that require modeling using graphs are clustering, ie. grouping data for the purpose of division according to some similarity criteria, pattern recognition that is closely related to clustering and modeling complex networks, whose application is common in network transport. Finally, an interactive application for calculating the graph spectrum was developed.

U ovom završnom radu definirat ćemo osnovne pojmove vezane uz Laplacijan grafa odnosno Laplaceovu matricu grafa. Opisat ćemo vezu Laplaceove matrice grafa sa matricom susjedstva i matricom incidencije, pokazati osnovna svojstva Laplacijana i reći nešto o svojstvenim vrijednostima Laplaceove matrice., In this nal work we will dene the basic terms that are con- nected to the Laplacian matrix of a graph. We will describe the Laplacian matrix with the help of adjacency matrix and the incidence matrix of a graph, show some basic properties of the Laplacian matrix and say something about the eigenvalues of the Laplacian matrix.

U ovom radu analizira se algoritam odred¯ivanja povezanosti decentraliziranog višeagentskog sustava u dinamiˇckoj topologiji korištenjem konsenzus algoritma zasnovanog na povjerenju. Promatrani grafovi su usmjereni, težinski i jednostavni te svaki agent izravno promatra svoje susjede dok se za informacije o ostalim agentima oslanja na informacije dobivene od svojih susjeda. Propagacija informacija uvelike ovisi o komunikacijskim performansama svakog pojedinog agenta, a brzina konvergencije lokalne matrice povezanosti ovisna je o topologiji grafa i broju agenata. In this thesis we consider and analyze algorithm for determining the connectivitiy of a decentralized multi-agent system in dynamic topology using consensus-based trust algorithm. Considered graphs are directed, weighted and simple, where every agent directly observes its neighbours while simultaneously relying on them to gather data about other agents. Propagation of information in given graph heavily depends on communication performance of every single agent and rate of convergence depends on topology of a given graph and on a number of agents in it.

U ovom radu korišten je multiagentski sustav s pet agenta te se promjenom opservacijske funkcije razmatrao njen utjecaj na konsenzus protokola po povjerenju.Općenito, zadatak opservacijske funkcije u multiagentskim sustavima jest da u što kraćem vremenu uspostavi što točnije povjerenje između svih agenata. Dosad je se kao opservacijska funkcija uglavnom koristila eksponencijalna funkcija 𝑓(𝛿/𝜎) = 𝑒−(𝛿/𝜎)^2 , pa je u ovom radu bilo razmatrano još pet funkcija koje su se uspoređivale s referentnom eksponencijalnom. Protokol za razvoj povjerenja implementiran je u programu Matlab te je analiziran utjecaj primjene različitih opservacijskih funkcija na brzinu i točnost konsenzus protokola. In this thesis it is used multi – agent system with five agents and then, as the observation function is changing, we have scrutinized its influence on consensus of the trust adaptation. Generally, the task of the observation function like itself in multi – agents systems is to establish big trusts between the agents as precisely as it can. Until now, there is commonly used exponential function 𝑓(𝛿/𝜎) = 𝑒−(𝛿/𝜎)^2 as the observation function, but in this thesis there is taken five more functions that were compared with the basic exponential function. Confidence development protocol is implemented in Matlab program and also there is analyzed an effect of application different observation functions on the speed and accuracy of the consensus protocol.

Ovaj rad prikazuje skup ljudi na društvenoj mreži Facebook koji su međusobno povezani prijateljstvima. Takvu mrežu moguće je prikazati na mnogo načina no ovaj rad se fokusira na 3 prikaza i njihova 3 algoritma optimizacije. Prikazi koji su korišteni su silom usmjereni razmještaj, prikaz matricom susjedstva i kružni razmještaj. Silom usmjereni razmještaj koristi ponašanje čestica u prirodi kao temeljnu ideju. Svaka čestica je jedan čvor u grafu te ima privlačnu silu prema čvorovima s kojima je povezana i odbojnu silu prema svim ostalim čvorovima. Nakon nekoliko iteracija algoritma čvorovi se grupiraju i vizualno odvoje od drugih grupa čvorova. Prikaz matricom susjedstva uzima numerirane čvorove kao retke i stupce matrice dok se popunjavaju ćelije u matrici ako su dva čvora povezana. Algoritam zamjeni redosljed redaka i stupaca u matrici kako bi ponovo iscrtana slika matrice bila preglednija. Kružni razmještaj poreda čvorove na kružnicu u početni položaj te također pomoću algoritma zamjeni redoslijed čvorova. Razlika u odnosu na matricu susjedstva je što kružni razmještaj uzima u obzir koordinate svakog čvora dok matrica susjedstva uzima u obzir isključivo udaljenost indeksa između čvorova. Svaki od prikaza ima svoje prednosti i nedostatke te je kroz obradu zaključeno koji prikaz je najpovoljniji za koju mrežu.

U ovom radu razmatra se problem uspostave povjerenja u multi-agentskim sustavima na temelju binarnog konsenzusa. Sustav od n agenata je na početku decentraliziran i svaki agent ima svoj vektor povjerenja prema ostalim agentima u sustavu. Tijekom simulacije agenti razmjenjuju informacije međusobnom komunikacijom i izravnim promatranjem svojih susjeda, te na temelju dobivenih informacija obnavljaju svoje vektore povjerenja. Kada se uspostavi konsenzus, odnosno kada vektori povjerenja svih agenata postanu jednaki, agent s najvećom vrijednosti povjerenja postaje vođa sustava. Primjenom binarnog protokola na algoritam za uspostavu povjerenja u sustavu osigurana je konvergencija povjerenja u konačnom vremenu. Binarni protokol je primijenjen i na sustav od 9 CASU jedinica gdje želimo da sve CASU jedinice u konačnom vremenu postignu zadanu referentnu temperaturu koja je unaprijed poznata samo jednoj od njih. Algoritam je implementiran u Matlab okruženju, te i u ASSISI simulatoru koji opisuje realni sustav. In this paper we consider the problem of trust development in multi-agent systems based on the binary consensus. At the beginning, the system consisting of n agents is decentralized. Every agent has its own trust vector containing trust values regarding every agent in the group. During the simulation agents exchange information by communication and local observations of their neighbours. Based on these exchanged information, they update their trust vectors. Once the consensus has been achieved and trust vectors of each agent have converged to the same value, the agent with the highest trust value becomes the leader of the system. By using the binary protocol, we guarantee the finite-time convergence of trust values. Moreover, binary protocol is applied to the system consisting of 9 CASU units. We want all CASU units to reach the given reference temperature in the finite time. Only one CASU unit knows what is the value of the reference temperature. Algorithm is implemented in Matlab environment and in the ASSISI simulator that describes the real system.