|
Algebraic Connectivity
The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph ' is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of '. This eigenvalue is greater than 0 if and only if ' is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is. It has been used in analyzing the robustness and synchronizability of networks. Properties The truncated icosahedron or Buckminsterfullerene graph has a traditional connectivity (graph theory)">connectivity of 3, and an algebraic connectivity of 0.243. The algebraic connectivity of undirected graphs with nonnegative weights is a(G)\geq0, with the inequality being strict if and only if is connected. However, the algebraic connectivity can be negative for gener ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Degree (graph Theory)
In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex v is denoted \deg(v) or \deg v. The maximum degree of a graph G is denoted by \Delta(G), and is the maximum of G's vertices' degrees. The minimum degree of a graph is denoted by \delta(G), and is the minimum of G's vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, every vertex has the same degree, and so we can speak of ''the'' degree of the graph. A complete graph (denoted K_n, where n is the number of vertices in the graph) is a special kind of regular graph where all vertices have the maximum possible degree, n-1. In a signed graph, the number of positive edges connected to the vertex v is called positive deg(v) and the number of connected negative edges is enti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algebraic Graph Theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph theory, involving the use of linear algebra, the use of group theory, and the study of graph invariants. Branches of algebraic graph theory Using linear algebra The first branch of algebraic graph theory involves the study of graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, or the Laplacian matrix of a graph (this part of algebraic graph theory is also called spectral graph theory). For the Petersen graph, for example, the spectrum of the adjacency matrix is (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Several theorems relate properties of the spectrum to other graph properties. As a simple example, a connected graph with diameter ''D'' wil ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Property
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.. Definitions While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph. Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant". More formally, a graph property is a class of graphs with the property that any two isomorphic gra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Connectivity (graph Theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more Connected component (graph theory), isolated subgraphs. It is closely related to the theory of flow network, network flow problems. The connectivity of a graph is an important measure of its resilience as a network. Connected vertices and graphs In an undirected graph , two vertex (graph theory), vertices and are called connected if contains a Path (graph theory), path from to . Otherwise, they are called disconnected. If the two vertices are additionally connected by a path of length (that is, they are the endpoints of a single edge), the vertices are called adjacent. A Graph (discrete mathematics), graph is said to be connected if every pair of vertices in the graph is connected. This means that there is a Path (graph theory), path between every ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Articulation Point
In graph theory, a biconnected component or block (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components. A block containing at most one cut vertex is called a leaf block, it corresponds to a leaf vertex in the block-cut tree. Algorithms Linear time depth-first search The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan (1973). It runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions). The idea is to run a depth-first sear ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Partition
In mathematics, a graph partition is the reduction of a Graph (discrete mathematics), graph to a smaller graph by partition of a set, partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see . Two common examples of graph partitioning are minimum cut and max ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Eigenvector
In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a constant factor \lambda when the linear transformation is applied to it: T\mathbf v=\lambda \mathbf v. The corresponding eigenvalue, characteristic value, or characteristic root is the multiplying factor \lambda (possibly a negative or complex number). Geometrically, vectors are multi- dimensional quantities with magnitude and direction, often pictured as arrows. A linear transformation rotates, stretches, or shears the vectors upon which it acts. A linear transformation's eigenvectors are those vectors that are only stretched or shrunk, with neither rotation nor shear. The corresponding eigenvalue is the factor by which an eigenvector is stretched or shrunk. If the eigenvalue is negative, the eigenvector's direction is reversed. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Isoperimetric Number
In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold. The Cheeger constant is named after the mathematician Jeff Cheeger. Definition Let be an undirected finite graph with vertex set and edge set . For a collection of vertices , let denote the collection of all edges going from a vertex in to a vertex outside of (sometimes called the ''edge boundary'' of ): :\partial A := \. Note that the edges are unordered, i.e., \ = \. The Cheeger constant of , denoted , is defined by :h(G) := \min \left\. The Cheeger constant is strictly positive if and only if is a connected graph. Intuit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distance (graph Theory)
In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance or shortest-path distance. Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite. In the case of a directed graph the distance between two vertices and is defined as the length of a shortest directed path from to consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs, does not necessarily coincide with —so it is just a quasi-metric, and it might be the case that one is defined while the other is not. Related concepts A metric space defined over a set of points in terms of distances in a graph defined ov ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kuramoto Model
The Kuramoto model (or Kuramoto–Daido model), first proposed by , is a mathematical model used in describing synchronization. More specifically, it is a model for the behavior of a large set of coupled oscillators. Its formulation was motivated by the behavior of systems of chemical and biological process, biological oscillators, and it has found widespread applications in areas such as Neural oscillation#Mathematical description, neuroscience and oscillating flame dynamics. Kuramoto was quite surprised when the behavior of some physical systems, namely coupled arrays of Josephson junctions, followed his model. The model makes several assumptions, including that there is weak coupling, that the oscillators are identical or nearly identical, and that interactions depend sinusoidally on the phase difference between each pair of objects. Definition In the most popular version of the Kuramoto model, each of the oscillators is considered to have its own intrinsic natural frequency ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
