Wyniki wyszukiwania - Biblioteka Nauki

1

An Oriented Version of the 1-2-3 Conjecture

100%

Baudon O. , Bensmail J. , Sopena É.

|

tom 35

|

nr 1

141-156

EN

The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an NP-complete problem. These results also hold for product or list versions of this problem.

2

Large minimal irregular digraphs

100%

Dziechcińska-Halamoda Z. , Majcher Z. , Michael J. , Skupień Z.

Opuscula Mathematica

|

2003

|

tom Vol. 23

21-24

EN

A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal if the removal of any arc results in a non-irregular digraph. A large minimal irregular digraph Fn of order n is constructed if n is the sum of initial positive integers. It is easily seen that the minimum and maximum sizes among n-vertex irregular digraphs are asymptotic to [formula] and n2, respectively. It appears that the size of Fn is asymptotic to n2, too. Similarly, a minimal irregular oriented graph Hn is constructed such that the size of Hn is asymptotic to 1/2n2 whence it is asymptotically the largest size among n-vertex oriented graphs whether irregular or not.

3

Independent Detour Transversals in 3-Deficient Digraphs

88%

van Aardt S. , Frick M. , Singleton J.

|

nr 2

261-275

EN

In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient if its order is exactly p more than the order of its longest paths. It follows easily from Havet’s result that for p = 1, 2 every p-deficient digraph has an independent detour transversal. This paper explores the existence of independent detour transversals in 3-deficient digraphs.

4

Every 8-Traceable Oriented Graph Is Traceable

88%

Aardt S. A. v.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 4

963-973

EN

A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8-traceable oriented graph is traceable.

5

Generations in Bayesian networks

75%

Litvinenko A. , Litvinenko N. , Mamyrbayev O. , Shayakhmetova A.

Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska

|

2019

|

tom T. 9, nr 3

10--13

EN

This paper focuses on the study of some aspects of the theory of oriented graphs in Bayesian networks. In some papers on the theory of Bayesian networks, the concept of “Generation of vertices” denotes a certain set of vertices with many parents belonging to previous generations. Terminology for this concept, in our opinion, has not yet fully developed. The concept of “Generation” in some cases makes it easier to solve some problems in Bayesian networks and to build simpler algorithms. In this paper we will consider the well-known example “Asia”, described in many articles and books, as well as in the technical documentation for various toolboxes. For the construction of this example, we have used evaluation versions of AgenaRisk.

PL

Niniejszy artykuł koncentruje się na badaniu pewnych aspektów teorii zorientowanych grafów w sieciach bayesowskich. W niektórych artykułach na temat teorii sieci bayesowskich pojęcie „generacji wierzchołków” oznacza pewien zestaw wierzchołków z wieloma rodzicami należącymi do poprzednich generacji. Terminologia tego pojęcia, naszym zdaniem, nie została jeszcze w pełni rozwinięta. Koncepcja „Generacji” w niektórych przypadkach ułatwia rozwiązywanie niektórych problemów w sieciach bayesowskich i budowanie prostszych algorytmów. W tym artykule rozważymy dobrze znany przykład „Azja”, opisany w wielu artykułach i książkach, a także w dokumentacji technicznej różnych zestawów narzędzi. Do budowy tego przykładu wykorzystaliśmy wersje testowe AgenaRisk.

6

Elementwise power losses calculation in complex distribution power networks represented by hierarchical-multilevel topology structure

51%

Asanova M. S. , Asanova S. M. , Safaraliev M. K. , Lyukhanov E. A. , Tavlintsev A. , Shelyug S. N.

Przegląd Elektrotechniczny

|

2021

|

tom R. 97, nr 11

106--110

EN

Complex ramified distribution power networks (DPN) 6-20 kV are characterized by large dimension, development dynamism, insufficient regime information completeness and reliability. Structured hierarchical-multilevel approach to the elementwise calculation of power losses in DPN is proposed. The DPN structural model is described. A substantive description of this approach is given on the example of ramified DPN with n nodes and m sections (transmission line and transformer) with a tree structure.

PL

Złożone rozgałęzione Sieci Elektroenergetyczne (DPN) 6-20 kV charakteryzują się dużym wymiarem, dynamiką rozwoju, niewystarczającą kompletnością informacji o reżimie i niezawodnością. Zaproponowano ustrukturyzowane hierarchiczno-wielopoziomowe podejście do pierwiastkowego obliczania strat mocy w DPN. Opisano model strukturalny DPN. Merytoryczny opis takiego podejścia podano na przykładzie rozgałęzionego DPN z węzłami n i odcinkami m (linia transmisyjna i transformator) o strukturze drzewa.