Wyniki wyszukiwania - Biblioteka Nauki

1

The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic

100%

Wang Y. , Fan Y.-Z. , Li X.-X. , Zhang F.-F.

|

tom 35

|

nr 2

249-260

EN

A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains exactly one cycle (namely the class Ucn of graphs whose complements are unicyclic), and characterize the unique minimizing graph in Ucn when n ≥ 20.

2

Construction of Cospectral Integral Regular Graphs

100%

Bapat R. B. , Karimi M.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 3

595-609

EN

Graphs G and H are called cospectral if they have the same characteristic polynomial. If eigenvalues are integral, then corresponding graphs are called integral graph. In this article we introduce a construction to produce pairs of cospectral integral regular graphs. Generalizing the construction of G4(a, b) and G5(a, b) due to Wang and Sun, we define graphs 𝒢4(G,H) and 𝒢5(G,H) and show that they are cospectral integral regular when G is an integral q-regular graph of order m and H is an integral q-regular graph of order (b − 2)m for some integer b ≥ 3.

3

Two Graphs with a Common Edge

88%

Badura L.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 3

497-507

EN

Let G = G1 ∪ G2 be the sum of two simple graphs G1,G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant det A(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples

4

Applications of Bipartite Graphs and their Adjacency Matrices to Covering-based Rough Sets

88%

Wang J. , Zhu W.

Fundamenta Informaticae

|

2017

|

tom Vol. 156, nr 2

237--254

EN

In this paper, bipartite graphs and their adjacency matrices are applied to equivalently represent covering-based rough sets through three sides, which are approximation operators, properties and reducible elements. Firstly, a bipartite graph is constructed through a covering. According to the constructed bipartite graph, two equivalent representations of a pair of covering upper and lower approximation operators are presented. And an algorithm is designed for computing the pair of covering approximation operators from the viewpoint of these equivalent representations. Some properties and reducible elements of covering-based rough sets are also investigated through the constructed bipartite graph. Finally, an adjacency matrix of the constructed bipartite graph is proposed, and reducible elements in the covering are obtained through the proposed adjacency matrix. Moreover, an equivalent representation of the covering upper approximation operator is presented through the proposed adjacency matrix. In a word, these results show two interesting views, which are graphs and matrices, to investigate covering-based rough sets.

5

The least eigenvalue of the graphs whose complements are connected and have pendent paths

88%

Wang C. , Yu G. , Sun W. , Cao J.

|

tom Vol. 8, No. 4

303--308

EN

The adjacency matrix of a graph is a matrix which represents adjacent relation between the vertices of the graph. Its minimum eigenvalue is defined as the least eigenvalue of the graph. Let Gn be the set of the graphs of order n, whose complements are connected and have pendent paths. This paper investigates the least eigenvalue of the graphs and characterizes the unique graph which has the minimum least eigenvalue in Gn.

6

The K4 graph and the inertia of the adjacency matrix for a connected planar graph

75%

Taliceo N. P. , Griffith D. A.

Studia komitetu przestrzennego zagospodarowania kraju PAN

|

2018

|

tom 183

185-209

7

On the eigenvalue distribution of adjacency matrices for connected planar graphs

75%

Griffith D. A.

Quaestiones Geographicae

|

2015

|

tom 34

|

nr 4

8

On the inverse of the adjacency matrix of a graph

75%

Farrugia A. , Gauci J. B. , Sciriha I.

Special Matrices

|

2013

|

tom 1

28-41

EN

A real symmetric matrix G with zero diagonal encodes the adjacencies of the vertices of a graph G with weighted edges and no loops. A graph associated with a n × n non–singular matrix with zero entries on the diagonal such that all its (n − 1) × (n − 1) principal submatrices are singular is said to be a NSSD. We show that the class of NSSDs is closed under taking the inverse of G. We present results on the nullities of one– and two–vertex deleted subgraphs of a NSSD. It is shown that a necessary and sufficient condition for two–vertex deleted subgraphs of G and of the graph ⌈(G−1) associated with G−1 to remain NSSDs is that the submatrices belonging to them, derived from G and G−1, are inverses. Moreover, an algorithm yielding what we term plain NSSDs is presented. This algorithm can be used to determine if a graph G with a terminal vertex is not a NSSD.

9

Efficient Implementation of the Italiano Algorithms for Updating the Transitive Closure on Associative Parallel Processors

63%

Nepomniaschay A.

|

tom Vol. 89, nr 2-3

313-329

EN

We propose a simple data structure for an efficient implementation of the Italiano algorithms for the dynamic updating of the transitive closure of a directed graph represented as adjacency matrix on a model of associative (or content addressable) parallel processors with vertical processing (the STAR–machine). Associative versions of the Italiano algorithms are represented as procedures DeleteArc1 and InsertArc1. We prove the correctness of these procedures and evaluate their time and space complexity. We also present the main advantages of associative versions of the Italiano algorithms.

10

Computational Classification of Tubular Algebras

63%

Dowbor P. , Kim Y.

Fundamenta Informaticae

|

2020

|

tom Vol. 177, nr 1

39--67

EN

The effective method (based on Theorem 5.3) of classifying tubular algebras by the Cartan matrices of tilting sheaves over weighted projective lines with all indecomposable direct summands in some finite “fundamental domain” , by the reduction to the two elementary problems of discrete mathematics having algorithmic solutions is presented in details (see Problem A and B). The software package CART_TUB being an implementation of this method yields the precise classification of all up to isomorphism tubular algebras of a fixed tubular type p, by creating the complete lists of their Cartan matrices, and furnish their tilting realizations. In particular, the number of isomorphism classes of tubular algebras of the type p is determined (Theorem 2.3).

11

The notation of mechanism structure in structural research

63%

Romaniak K.

|

tom Vol. 25

3--10

EN

Different methods of notation are in use when describing the construction of mechanisms in structural research. This work deals with the issue of notation and presents: – constructional drawing in which the construction of the mechanism is detailed by the use of the Monge’s projection (views, projections), axonometric or perspective projections; – kinematic diagram in which kinematic pairs and links are described by symbols. Given dimensions of individual links allow to specify the positioning of specific parts of the mechanism depending on the movement of input links; – structural diagram in which the class of each kinematic pair is specified; – structural graph in a form of a polygon in which its sides and vertices correspond with kinematic pairs and links respectively; – adjacency matrix in a form of a square matrix in which the number of rows and columns corresponds with the number of links in the mechanism. Its elements are: 0 when links are not joined, or 1 when links are joined; – loop notation in which links and kinematic pairs that form individual closed contours of the mechanism are given; – author’s notation of the construction of spatial mechanisms, in which the classes of kinematic pairs are presented in a form of labels next to their graphic representation.

PL

Praca poświęcona jest różnym sposobom zapisu mechanizmów, używanych w badaniach strukturalnych. Przedstawiono: – zapis konstrukcyjny, w którym używając rzuty prostokątne (widoki, przekroje) oraz aksonometrię przedstawia się szczegółowo budowę mechanizmu;

12

Sprzętowa implementacja zachłannego algorytmu kolorowania grafu

44%

Wyrwoł B.

Elektronika : konstrukcje, technologie, zastosowania

|

2010

|

tom Vol. 51, nr 9

21-23

PL

Kolorowanie grafów znajduje zastosowanie wszędzie tam, gdzie konieczny jest podział zbioru na rozłączne podzbiory wg określonego kryterium jakie spełniają lub nie elementy zbioru. Większość algorytmów kolorowania realizowana jest zwykle na drodze programowej. W sytuacji, kiedy dużą rolę odgrywają uwarunkowania czasowe, konieczna jest realizacja sprzętowa z wykorzystaniem dedykowanego układu. W artykule przedstawiony został zachłanny algorytm kolorowania wierzchołków grafu oraz jego sprzętowa implementacja w układzie programowalnym FPGA. Dodatkowo omówiona została metoda reprezentacji danych opisujących strukturę grafu i przykład wykorzystania sprzętowego modułu kolorowania grafu, wspomagającego proces dekompozycji lingwistycznej, w systemie wnioskowania przybliżonego.

EN

Graph coloring algorithms are used wherever it is necessary to divide set on disjoint subsets according to specified criteria or not they meet the elements of the set. Most of the coloring algorithms are usually implemented as a computer or microcontroller program. To reduce computing time of the coloring result it is necessary to implement hardware using a dedicated chip. The paper presents graph greedy vertex algorithm and its hardware implementation in an FPGA chip. It describes also a graph data structure and finally implementation of the graph coloring module in the fuzzy hierarchical inference system. It is used in linguistic decomposition process of the knowledge base in the stage of the partitioning the rule base.