Iskanje po katalogu digitalne knjižnice

Opis: This doctoral dissertation is concerned with aspects on distance related topics in graphs. We study three main topics, namely a recently introduced measure called the Hausdorff distance of graphs and two new graph invariants - the edge metric dimension and the mixed metric dimension of graphs. All three topics are part of the metric graph theory since they are tightly connected with the basic concept of distance between two vertices of a graph. The Hausdorff distance is a relatively new measure of the similarity of graphs. The notion of the Hausdorff distance considers a special kind of common subgraph of the compared graphs and depends on the structural properties outside of the common subgraph. We study the Hausdorff distance between certain families of graphs that often appear in chemical graph theory. Next to a few results for general graphs, we determine formulae for the distance between paths and cycles. Previously, there was no known efficient algorithm for the problem of determining the Hausdorff distance between two trees, and in this dissertation we present a polynomial-time algorithm for it. The algorithm is recursive and it utilizes the divide and conquer technique. As a subtask it also uses a procedure that is based on the well-known graph algorithm for finding a maximum bipartite matching. The edge metric dimension is a graph invariant that deals with distinguishing the edges of a graph. Let $G=(V(G),E(G))$ be a connected graph, let $w \in V(G)$ be a vertex, and let $e=uv \in E(G)$ be an edge. The distance between the vertex $w$ and the edge $e$ is given by $d_G(e,w)=\min\{d_G(u,w),d_G(v,w)\}$. A vertex $w \in V(G)$ distinguishes two edges $e_1,e_2 \in E(G)$ if $d_G(w,e_1) \ne d_G(w,e_2)$. A set $S$ of vertices in a connected graph $G$ is an edge metric generator of $G$ if every two distinct edges of $G$ are distinguished by some vertex of $S$. The smallest cardinality of an edge metric generator of $G$ is called the edge metric dimension and is denoted by $dim_e(G)$. The concept of the edge metric dimension is new. We study its mathematical properties. We make a comparison between the edge metric dimension and the standard metric dimension of graphs while presenting some realization results concerning the two. We prove that computing the edge metric dimension of connected graphs is NP-hard and give some approximation results. Moreover, we present bounds and closed formulae for the edge metric dimension of several classes of graphs. The mixed metric dimension is a graph invariant similar to the edge metric dimension that deals with distinguishing the elements (vertices and edges) of a graph. A vertex $w \in V(G)$ distinguishes two elements of a graph $x,y \in E(G)\cup V(G)$ if $d_G(w,x) \ne d_G(w,y)$. A set $S$ of vertices in a connected graph $G$ is a mixed metric generator of $G$ if every two elements $x,y \in E(G) \cup V(G)$ of $G$, where $x \neq y$, are distinguished by some vertex of $S$. The smallest cardinality of a mixed metric generator of $G$ is called the mixed metric dimension and is denoted by $dim_m(G)$. In this dissertation, we consider the structure of mixed metric generators and characterize graphs for which the mixed metric dimension equals the trivial lower and upper bounds. We also give results on the mixed metric dimension of certain families of graphs and present an upper bound with respect to the girth of a graph. Finally, we prove that the problem of determining the mixed metric dimension of a graph is NP-hard in the general case.
Ključne besede: Hausdorff distance, distance between graphs, graph algorithms, trees, graph similarity, edge metric dimension, edge metric generator, mixed metric dimension, metric dimension
Objavljeno v DKUM: 03.08.2020; Ogledov: 1587; Prenosov: 124
Celotno besedilo (800,48 KB)

Opis: In this research, machine learning algorithms were compared in a landslide-susceptibility assessment. Given the input set of GIS layers for the Starča Basin, which included geological, hydrogeological, morphometric, and environmental data, a classification task was performed to classify the grid cells to: (i) landslide and non-landslide cases, (ii) different landslide types (dormant and abandoned, stabilized and suspended, reactivated). After finding the optimal parameters, C4.5 decision trees and Support Vector Machines were compared using kappa statistics. The obtained results showed that classifiers were able to distinguish between the different landslide types better than between the landslide and non-landslide instances. In addition, the Support Vector Machines classifier performed slightly better than the C4.5 in all the experiments. Promising results were achieved when classifying the grid cells into different landslide types using 20% of all the available landslide data for the model creation, reaching kappa values of about 0.65 for both algorithms.
Ključne besede: landslides, support vector machines, decision trees classifier, Starča Basin
Objavljeno v DKUM: 13.06.2018; Ogledov: 1268; Prenosov: 66
Celotno besedilo (382,76 KB)
Gradivo ima več datotek! Več...

Opis: Background and Goal: The article is aimed at conducting an empirical analysis of the value and significance of coopetitors’ attributes thanks to which coopetition, which is a combination of cooperation and competition between competitors, generates a substantial corporate profit. Four major competitors’ attributes have been analysed: its size, geographical scope, market and technological position. The research also includes the Porter’s value chain. Design/ Methodology/Approach: The survey has been conducted on a sample of 235 high- tech companies operating in Poland and involved in coopetition. The sample is representative. The data have been collected at interviews with company top executives or owners. The research applies the method of classification trees, which, thanks to diagrams, sequentially divides the examined data space into classes (spaces) of similar properties. The assessment of the effect of coopetition, including its variants, made by the examined company served as a dependent qualitative variable. Four coopetitor’s attributes and their variants were assumed as explanatory variables (predictors) affecting the assessment of cooperation. Results: The results of research indicated the necessity for an accurate competitor’s profile selection. The significance of each of the four attributes may be different depending on the undertaken areas of cooperation with a competitor. The value of all the attributes of competitors is also diverse depending on the area of cooperation. A selected competitor’s profile with regard to the four analysed attributes may become a stimulant to generate benefits in one area, while in another area it may become an inhibitor. Conclusions: So far, the selection of a coopetition partner has been treated universally, without scrutinizing on some specific needs in relation to the area of cooperation. The selection of an appropriate coopetitor’s profile will allow for the cost reduction in search of appropriate candidates for cooperation and in relations management.
Ključne besede: coopetition, effects, competitor’s attributes, classification trees
Objavljeno v DKUM: 29.11.2017; Ogledov: 1110; Prenosov: 192
Celotno besedilo (1,04 MB)
Gradivo ima več datotek! Več...

Opis: The domination game is played on a graph ▫$G$▫ by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on ▫$G$▫ and both players play optimally is the graph invariant ▫$\gamma_g(G)$▫, named the game domination number. Here we study the ▫$\gamma_g$▫-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize ▫$\gamma_g$▫-critical graphs with ▫$\gamma_g =2$▫ and with ▫$\gamma_g =3$▫, moreover for each ▫$n$▫ we identify the (infinite) class of all ▫$\gamma_g$▫-critical ones among the ▫$n$▫th powers ▫$C_N^n$▫ of cycles. Along the way we determine ▫$\gamma_g(C_N^n)$▫ for all ▫$n$▫ and ▫$N$▫. Results of a computer search for ▫$\gamma_g$▫-critical trees are presented and several problems and research directions are also listed.
Ključne besede: domination game, domination game critical graphs, powers of cycles, trees
Objavljeno v DKUM: 31.03.2017; Ogledov: 1295; Prenosov: 402
Celotno besedilo (194,74 KB)
Gradivo ima več datotek! Več...

Opis: Delne kocke so grafi, ki dopuščajo izometrične vložitve v hiperkocke. V članku so vpeljane ▫$Theta$▫-gracilne označitve delnih kock kot naravna razširitev gracilnih označitev dreves. Pokazano je, da so različni razredi delnih kock ▫$Theta$▫-gracilni, na primer sodi cikli, Fibonaccijeve kocke in (na novo vpeljane) leksikografske podkocke. Kartezični produkt ▫$Theta$▫-gracilnih delnih kock je spet tak in sprašujemo se, ali je morda vsaka delna kocka ▫$Theta$▫-gracilna. Pokazana je povezava med ▫$Theta$▫-gracilnimi označitvami in reprezentacijami celih števil v določenih številskih sistemih. Predlaganih je tudi nekaj smeri za nadaljnje raziskovanje.
Ključne besede: matematika, teorija grafov, drevesa, Ringel-Kotzigova domneva, delne kocke, Fibonaccijeve kocke, hiperkocke, mathematics, graph theory, graceful labelings, trees, Ringel-Kotzig conjecture, partial cubes, Fibonacci cubes, hypercubes
Objavljeno v DKUM: 10.07.2015; Ogledov: 1101; Prenosov: 50
Povezava na celotno besedilo