Search results for "adjacency matrix"

Two graphs with a common edge

2014

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

Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity

2016

Span program is a linear-algebraic model of computation which can be used to design quantum algorithms. For any Boolean function there exists a span program that leads to a quantum algorithm with optimal quantum query complexity. In general, finding such span programs is not an easy task. In this work, given a query access to the adjacency matrix of a simple graph G with n vertices, we provide two new span-program-based quantum algorithms:an algorithm for testing if the graph is bipartite that uses $$On\sqrt{n}$$ quantum queries;an algorithm for testing if the graph is connected that uses $$On\sqrt{n}$$ quantum queries.

P-matrix completions under weak symmetry assumptions

2000

An n-by-n matrix is called a Π-matrix if it is one of (weakly) sign-symmetric, positive, nonnegative P-matrix, (weakly) sign-symmetric, positive, nonnegative P0,1-matrix, or Fischer, or Koteljanskii matrix. In this paper, we are interested in Π-matrix completion problems, that is, when a partial Π-matrix has a Π-matrix completion. Here, we prove that a combinatorially symmetric partial positive P-matrix has a positive P-matrix completion if the graph of its specified entries is an n-cycle. In general, a combinatorially symmetric partial Π-matrix has a Π-matrix completion if the graph of its specified entries is a 1-chordal graph. This condition is also necessary for (weakly) sign-symmetric …

Network Entropy for the Sequence Analysis of Functional Connectivity Graphs of the Brain

2018

Dynamic representation of functional brain networks involved in the sequence analysis of functional connectivity graphs of the brain (FCGB) gains advances in uncovering evolved interaction mechanisms. However, most of the networks, even the event-related ones, are highly heterogeneous due to spurious interactions, which bring challenges to revealing the change patterns of interactive information in the complex dynamic process. In this paper, we propose a network entropy (NE) method to measure connectivity uncertainty of FCGB sequences to alleviate the spurious interaction problem in dynamic network analysis to realize associations with different events during a complex cognitive task. The p…

Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness

2016

We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time and using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.

Laplacian versus Adjacency Matrix in Quantum Walk Search

2015

A quantum particle evolving by Schr\"odinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs, and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Lapla…

Table of Periodic Properties of Fullerenes Based on Structural Parameters.

2004

The periodic table (PT) of the elements suggests that hydrogen could be the origin of everything else. The construction principle is an evolutionary process that is formally similar to those of Darwin and Oparin. The Kekulé structure count and permanence of the adjacency matrix of fullerenes are related to structural parameters involving the presence of contiguous pentagons p, q and r. Let p be the number of edges common to two pentagons, q the number of vertices common to three pentagons, and r the number of pairs of nonadjacent pentagon edges shared between two other pentagons. Principal component analysis (PCA) of the structural parameters and cluster analysis (CA) of the fullerenes perm…

2021

This paper proposes a new method for blind mesh visual quality assessment (MVQA) based on a graph convolutional network. For that, we address the node classification problem to predict the perceived visual quality. First, two matrices representing the 3D mesh are considered: a graph adjacency matrix and a feature matrix. Both matrices are used as input to a shallow graph convolutional network. The network consists of two convolutional layers followed by a max-pooling layer to provide the final feature representation. With this structure, the Softmax classifier predicts the quality score category without the reference mesh’s availability. Experiments are conducted on four publicly available …

Circular law for sparse random regular digraphs

2020

Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices. We show that, as long as $d\to\infty$ with $n$, the empirical spectral distribution of appropriately rescaled matrix $A_n$ converges weakly in probability to the circular law. This result, together with an earlier work of Cook, completely settles the problem of weak convergence of the empirical distribution in directed $d$-regular setting with the degree tending to infinity. As a crucial element of our proof, we develop a technique of bounding intermediate singular values of $A_n$ based on studyi…

3D-Chiral quadratic indices of the ‘molecular pseudograph’s atom adjacency matrix’ and their application to central chirality codification: classific…

2004

Quadratic indices of the 'molecular pseudograph's atom adjacency matrix' have been generalized to codify chemical structure information for chiral drugs. These 3D-chiral quadratic indices make use of a trigonometric 3D-chirality correction factor. These indices are nonsymmetric and reduced to classical (2D) descriptors when symmetry is not codified. By this reason, it is expected that they will be useful to predict symmetry-dependent properties. 3D-Chirality quadratic indices are real numbers and thus, can be easily calculated in TOMOCOMD-CARDD software. These descriptors circumvent the inability of conventional 2D quadratic indices (Molecules 2003, 8, 687-726. http://www.mdpi.org) and othe…