在張宜武教授的博士論文中研究到視線表示法和視線數。我們以類似的方法定義有向圖的表示法和有向圖的視線數。 首先，我們定義有向圖的視線數為b(Ｄ) ，Ｄ為有方向性的圖，在論文中可得b(Ｄ)≦┌1/2max｛△﹢(Ｄ),△﹣(Ｄ)｝┐。另一個重要的結論為考慮一個平面有向圖Ｄ，對圖形Ｄ上所有的點v，離開點v的邊（進入的邊）是緊鄰在一起時，則可得有向圖的視線數在這圖形上是１（即 b(Ｄ)=1）。 另外對特殊的圖形也有其不同的視線數，即對有向完全偶圖Ｄm,n ，b(Ｄm,n)≦┌1/2min｛m,n｝┐ ，而對競賽圖Ｄn ，可得b(Ｄn)≦┌n/3┐+1。 / In [2], Chang stuidied the bar visibility representations and defined bar visibility number.We defined analogously the bar visibility representation and the bar visibility number of a directed graph Ｄ. First we show that the bar visibility number, denoted by b(Ｄ),is at most ┌1/2max｛△﹢(Ｄ),△﹣(Ｄ)｝┐ if D is an oriented graph.And we show that b(Ｄ)=1 for the oriented planar graphs in which all outgoing (incoming) edges of any vertex v of Ｄ appear consecutively around v.For any complete bipartite digraph Ｄm,n ，b(Ｄm,n)≦┌1/2min｛m,n｝┐.For any tournament Ｄn,b(Ｄn)≦┌n/3┐+1.

The closed neighbourhood of a vertex in a graph is the vertex together with the set of adjacent vertices. A di®erentiating-dominating set, or identifying code, is a collection of vertices whose intersection with the closed neighbour- hoods of each vertex is distinct and nonempty. A di®erentiating-dominating set in a graph serves to uniquely identify all the vertices in the graph. Chapter 1 begins with the necessary de¯nitions and background results and provides motivation for the following chapters. Chapter 1 includes a summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de- ¯nes co-distinguishable graphs and determines bounds on the number of edges in graphs which are distinguishable and co-distinguishable while Chap- ter 3 describes the maximum number of vertices needed in order to identify vertices in a graph, and includes some Nordhaus-Gaddum type results for the sum and product of the di®erentiating-domination number of a graph and its complement. Chapter 4 explores criticality, in which any minor modi¯cation in the edge or vertex set of a graph causes the di®erentiating-domination number to change. Chapter 5 extends the identi¯cation parameters to allow for orientations of the graphs in question and considers the question of when adding orientation helps reduce the value of the identi¯cation parameter. We conclude with a survey of complexity results in Chapter 6 and a collection of interesting new research directions in Chapter 7. / Mathematical Sciences / PhD (Mathematics)

The closed neighbourhood of a vertex in a graph is the vertex together with the set of adjacent vertices. A di®erentiating-dominating set, or identifying code, is a collection of vertices whose intersection with the closed neighbour- hoods of each vertex is distinct and nonempty. A di®erentiating-dominating set in a graph serves to uniquely identify all the vertices in the graph. Chapter 1 begins with the necessary de¯nitions and background results and provides motivation for the following chapters. Chapter 1 includes a summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de- ¯nes co-distinguishable graphs and determines bounds on the number of edges in graphs which are distinguishable and co-distinguishable while Chap- ter 3 describes the maximum number of vertices needed in order to identify vertices in a graph, and includes some Nordhaus-Gaddum type results for the sum and product of the di®erentiating-domination number of a graph and its complement. Chapter 4 explores criticality, in which any minor modi¯cation in the edge or vertex set of a graph causes the di®erentiating-domination number to change. Chapter 5 extends the identi¯cation parameters to allow for orientations of the graphs in question and considers the question of when adding orientation helps reduce the value of the identi¯cation parameter. We conclude with a survey of complexity results in Chapter 6 and a collection of interesting new research directions in Chapter 7. / Mathematical Sciences / PhD (Mathematics)

We define a variation of injective oriented colouring as reflexive injective oriented colouring, or rio-colouring for short, which requires an oriented colouring to be injective on the neighbourhoods of the underlying graph, without requiring the colouring to be proper. An analysis of the complexity of the problem of deciding whether an oriented graph has a k-rio-colouring is considered, and we find a dichotomy for the values of k below 3 and above, being in P or NP-complete, respectively. Characterizations are given for the oriented graphs resulting from the polynomial-time solvable cases, and bounds are given for the rio-chromatic number in terms of maximum in-degree and out-degree, in general, and for oriented trees. Also, a polynomial-time algorithm is developed to aid in the rio-colouring of oriented trees.

This diploma thesis deals with an oriented graph processing applying a multi-agent system designated for traffic simulation. The thesis was written as a research study. Based on the study, a simulation environment was created able to respond to various stimuli. Meant as the agents, there are vehicles and their drivers that have various features, based on which they respond to the given stimuli. Communication is conducted via a so-called super-agent that monitors all action on the map and passes this information on particular agents. The agents are able to respond in advance to traffic jams (closures, accidents). In such situations, an algorithm designated for a new route finding is conducted. Besides the controlled ones, there can operate on the map also agents simulating common traffic.