Browsing by Subject "graph"

Now showing 1 - 20 of 36

Access status: Open Access ,
A note on M2-edge colorings of graphs
(2015) Czap, Július
An edge coloring $\varphi$ of a graph $G$ is called an $M_2$-edge coloring if $|\varphi(v)|\le2$ for every vertex $v$ of $G$, where $\varphi(v)$ is the set of colors of edges incident with $v$. Let $K_{2}(G)$ denote the maximum number of colors used in an $M_2$-edge coloring of $G$. Let $G_1$, $G_2$ and $G_3$ be graphs such that $G_1\subseteq G_2\subseteq G_3$. In this paper we deal with the following question: Assuming that $K_2(G_1)=K_2(G_3)$, does it hold $K_2(G_1)=K_2(G_2)=K_2(G_3)$?
Access status: Open Access ,
A note on Vizing's generalized conjecture
(2007) Blidia, Mostafa; Chellali, Mustapha
In this note we give a generalized version of Vizing's conjecture concerning the distance domination number for the cartesian product of two graphs.
Access status: Open Access ,
Application of selected methods of graph theory and combinatorial heuristics to minimising the number of transits nodes in an air network
(AGH University of Science and Technology Press, 2008) Mażbic-Kulma, Barbara; Owsiński, Jan Wojciech; Sęp, Krzysztof
In the paper we present the notion of alpha-clique and some of its properties. Covering with alpha-cliques is a preprocessing method for an air network, described as a graph, in which vertices correspond to airports and edges correspond to air connections. Using the alpha-clique cover we obtain a hypergraph, in which we find the minimum transversal. The set of vertices thus obtained is the sought-for set of transits nodes, called hubs. Using the alpha-clique concept instead of proper cliques we can obtain the solution to the graph covering problem easier.
Access status: Restricted ,
Dowody o wiedzy zerowej Hipoteza Bluma
(Data obrony: 2010-06-28) Petecki, Paweł
Wydział Matematyki Stosowanej
Access status: Open Access ,
Graph based image segmentation
(Wydawnictwa AGH, 2011) Fabijańska, Anna
In this paper problem of graph-based image segmentation was regarded. Specifically, min-cut/max-flow approach proposed by Boykov and Jolly was investigated. The influence of functions describing boundary and regional conditions on results of image segmentation of various images were presented and discussed.
Access status: Restricted ,
Hipoteza Erdősa-Sós
(Data obrony: 2009-10-15) Pieczka, Marcelina
Wydział Matematyki Stosowanej
Access status: Open Access ,
Intelligent city lighting supported by graph-based multiagent system
(Wydawnictwa AGH, 2013) Sędziwy, Adam; Kotulski, Leszek
Rosnące koszty energii, a także troska o środowisko naturalne stymulują rozwój technologii zmniejszających zużycie energii. W artykule dyskutowany jest inteligentny system oświetlenia miejskiego, którego celem jest dostosowywanie pracy oświetlenia do aktualnych potrzeb. Osiąga się to przez podejmowanie odpowiednich akcji w warunkach zmiany stanu środowiska, ale także przez predykcję jego stanu, na podstawie otrzymywanych danych sensorycznych. Złożoność obliczeniowa tak postawionego zadania sterowania wymaga użycia formalnego modelu systemu, pozwalającego na dekompozycję problemu i zrównoleglenie obliczeń.
Access status: Restricted ,
Listowe wersje addytywnych etykietowań rozróżniających sąsiadów w grafach
(Data obrony: 2015-07-16) Pietrucha, Wojciech
Wydział Matematyki Stosowanej
Access status: Restricted ,
Metody wyznaczania czasów przejazdów przy wykorzystaniu map cyfrowych
(Data obrony: 2017-07-10) Łukasik, Piotr
Wydział Geologii, Geofizyki i Ochrony Środowiska
Niniejsza praca rozwija tematykę metod wyznaczania czasów przejazdów przy wykorzystaniu map cyfrowych. Głównym celem było porównanie dostępnych algorytmów oraz programów oferujących możliwości wyznaczenia przejazdu pomiędzy zadanymi punktami. W przeprowadzonej analizie, spośród środowisk zarówno komercyjnych jak i darmowych, skupiono się na oprogramowaniu Open Source Routing Machine (w skrócie OSRM). Powodem tego wyboru były szerokie możliwości tego rozwiązania, począwszy od mechanizmu wgrywania własnych podkładów mapowych, szczegółowej konfiguracji prędkości na poszczególnych odcinkach, a skończywszy na licencji pod którą wydawany jest OSRM, czyli „BSD 2-clause”, pozwalającej na dowolne modyfikacje kodu oraz prywatne użycie. Eksperymentalne sprawdzenie tego rozwiązania dowiodło, że zachowuje się bardziej wydajnie pod względem czasu obliczania przejazdu, niż ma to miejsce w dostępnych zewnętrznych serwisach.
Access status: Open Access ,
Model formalny dla problemu lokalizacji błędów w kodzie programu
(Wydawnictwa AGH, 2007) Dereniowski, Dariusz; Kubale, Marek
There are several criteria for testing program correctness. In this paper we deal with the problem of automatic software testing under the assumption that the set of tests (assertions) is given for selected blocks of code. We simplify the analysis by assuming that the program being tested contains exactly one bug, but this does not lead to loss of generality. We consider some practical aspects of the above problem and a graph-theoretical model in general as well as some chromatic aspects of a graph searching model in particular.
Access status: Restricted ,
O grafach objazdowo jednorodnych
(Data obrony: 2012-10-29) Ślęzak, Piotr
Wydział Matematyki Stosowanej
Access status: Restricted ,
O liczbie trójkątów w grafach bez $C_{5}$ i o liczbie $C_{5}$ w grafach bez trójkątów
(Data obrony: 2019-03-14) Gryz, Olga
Wydział Matematyki Stosowanej
Access status: Restricted ,
O problemie strażników w galeriach sztuki z filarami
(Data obrony: 2015-07-20) Bury, Justyna
Wydział Matematyki Stosowanej
Access status: Restricted ,
O skojarzeniach w grafach
(Data obrony: 2011-07-07) Żupnik, Magdalena; Uzar, Jakub; Widuch, Justyna
Wydział Matematyki Stosowanej
Access status: Restricted ,
O skojarzeniach w grafach
(Data obrony: 2011-07-07) Widuch, Justyna; Uzar, Jakub; Żupnik, Magdalena
Wydział Matematyki Stosowanej
Access status: Restricted ,
O skojarzeniach w grafach
(Data obrony: 2011-07-07) Uzar, Jakub; Widuch, Justyna; Żupnik, Magdalena
Wydział Matematyki Stosowanej
Access status: Open Access ,
On graph models in knowledge engineering
(Wydawnictwa AGH, 2023) Ligęza, Antoni; Adrian, Weronika Teresa; Adrian, Marek; Kluza, Krzysztof; Jobczyk, Krystian; Wiśniewski, Piotr; Ślażyński, Mateusz; Jemioło, Paweł; Sepioło, Dominik; Stachura-Terlecka, Bernadetta; Zaremba, Mateusz; Szymkowski, Mateusz; Suchenia, Anna; Potempa, Tomasz
The paper presents selected applications of graph models in knowledge engineering. Starting from the basic definition of a graph as a set of nodes connected by edges, the article presents possible extensions of this concept aimed at increasing the power of expression and the ability to process knowledge. In particular, the work focuses on selected applications of graph models in research areas explored by the members of the KRaKEn research team.
Access status: Open Access ,
On the crossing numbers of join products of five graphs of order six with the discrete graph
(Wydawnictwa AGH, 2020) Staš, Michal
The main purpose of this article is broaden known results concerning crossing numbers for join of graphs of order six. We give the crossing number of the join product $G^{\ast}+D_{n}$, where the disconnected graph $G^{\ast}$ of order six consists of one isolated vertex and of one edge joining two nonadjacent vertices of the $5$-cycle. In our proof, the idea of cyclic permutations and their combinatorial properties will be used. Finally, by adding new edges to the graph $G^{\ast}$, the crossing numbers of $G_{i}+D_{n}$ for four other graphs $G_{i}$ of order six will be also established.
Access status: Open Access ,
On the crossing numbers of join products of W4+Pn and W4+Cn
(Wydawnictwa AGH, 2021) Staš, Michal; Valiska, Juraj
The crossing number $cr(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. The main aim of the paper is to give the crossing number of the join product $W_{4}+P_{n}$ and $W_{4}+C_{n}$ for the wheel $W_4$ on five vertices, where $P_n$ and $C_n$ are the path and the cycle on $n$ vertices, respectively. Yue et al. conjectured that the crossing number of $W_{m}+C_{n}$ is equal to $Z(m+1)Z(n)+(Z(m)-1) \big \lfloor \frac{n}{2} \big \rfloor + n+ \big\lceil\frac{m}{2}\big\rceil +2$, for all $m,n \geq 3$, and where the Zarankiewicz's number $Z(n)=\big \lfloor \frac{n}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor$ is defined for $n \geq 1$. Recently, this conjecture was proved for $W_{3}+C_{n}$ by Klešč. We establish the validity of this conjecture for $W_{4}+C_{n}$ and we also offer a new conjecture for the crossing number of the join product $W_{m}+P_{n}$ for $m \geq 3$ and $n \geq 2$.
Access status: Open Access ,
On the hat problem on a graph
(2012) Krzywkowski, Marcin
The topic of this paper is the hat problem in which each of $n$ players is uniformly and independently fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of winning. In this version every player can see everybody excluding himself. We consider such a problem on a graph, where vertices correspond to players, and a player can see each player to whom he is connected by an edge. The solution of the hat problem on a graph is known for trees and for cycles on four or at least nine vertices. In this paper first we give an upper bound on the maximum chance of success for graphs with neighborhood-dominated vertices. Next we solve the problem on unicyclic graphs containing a cycle on at least nine vertices. We prove that the maximum chance of success is one by two. Then we consider the hat problem on a graph with a universal vertex. We prove that there always exists an optimal strategy such that in every case some vertex guesses its color. Moreover, we prove that there exists a graph with a universal vertex for which there exists an optimal strategy such that in some case no vertex guesses its color. We also give some Nordhaus-Gaddum type inequalities.