China
Africa
Explore chapters and articles related to this topic
Introduction to graph theory
Published in Karthik Raman, An Introduction to Computational Systems Biology, 2021
A bipartite graph is a special type of graph, where there are two disjoint independent3 sets of nodes, such that no two nodes within the same set have edges between them. Bipartite graphs arise naturally in scenarios where there are two types of objects (e.g. flights and airports, or actors and movies), or two sets of people (e.g. men and women). Film actor networks are bipartite, where the two sets of nodes represent actors and movies, and edges connect actors to the movies they starred in. Bipartite graphs are two-colourable, in that every node can be assigned a colour such that no two adjacent nodes in the entire graph have the same colour. It is also helpful to think of this in terms of shapes—a graph of squares and ellipses, where no ellipse is adjacent to another ellipse, and no square is connected to another square (as we will see in Figure 2.10). Bipartite graphs are also very useful to represent a wide range of biological networks, capturing diverse kinds of information, ranging from disease–gene networks or drug–target networks (§4.2), to metabolic networks (§2.5.5). It is possible to make projections of bipartite graphs, to compress the information. Naturally, two different projections are possible, for each node type (colour/shape)—the edges in the projection connect every pair of nodes that were separated by two edges in the bipartite graph. We will discuss examples in §4.4.2.
Deployment, Patrolling and Foraging
Published in Yasmina Bestaoui Sebbane, Multi-UAV Planning and Task Allocation, 2020
In order to find the optimal locations of UAVs functioning as communication relays at a fixed position between stationary nodes, the performance index for network connectivity is used. As the number of nodes increases, network complexity increases. Thus, the concept of minimum spanning tree can be used to obtain the highest probability of a successful transmission using minimum possible links. A spanning tree is a subgraph that is itself a tree connecting all the vertices of the graph together. For a successful transmission, the weight of each graph node is Wij=-logPrij
Deployment, Patrolling, and Foraging
Published in Yasmina Bestaoui Sebbane, Intelligent Autonomy of Uavs, 2018
Optimal UAV deployment for stationary nodes In order to find the optimal locations of UAVs functioning as communication relays at a fixed position between stationary nodes, the performance index for network connectivity is used. As the number of nodes increases, network complexity increases. Thus, the concept of minimum spanning tree can be used to obtain the highest probability of a successful transmission using minimum possible links. A spanning tree is a sub-graph that is itself a tree connecting all the vertices of the graph together. For a successful transmission, the weight of each graph node is Wij=-logPrij $$ \begin{aligned} W_{ij} = - log P_r^{ij} \end{aligned} $$
Distributed maximal independent set computation driven by finite-state dynamics
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Eric Goles, Laura Leal, Pedro Montealegre, Ivan Rapaport, Martín Ríos-Wilson
In this article, all graphs are simple, finite, and undirected. Given a node v of a graph , the neighborhood ofv, denoted by , is the set of vertices adjacent to v. Formally . The degree of a node u, denoted is the cardinality of . Given a set of nodes , the subgraph of G induced byU, denoted , is the graph defined by the vertex set U, and all the edges in E with both endpoints in U. A graph is called connected if there is a path between every pair of vertices. A connected component of a graph G is an inclusion maximal connected set of vertices. A connected graph without cycles is called a tree. A graph where every node has degree d is called d-regular.
A new approach in developing an urban rail transit emergency knowledge graph based on operation fault logs
Published in Journal of Transportation Safety & Security, 2022
Bosong Fan, Chunfu Shao, Yutong Liu, Juan Li
A spanning tree is a subgraph of a connected graph that contains all nodes connected to as few edges as possible. A directed connected graph can be represented by its node set and directed edge set Each directed edge has a score Here, we define a MST as a directed connected graph that maximizes the sum of the scores of the node set containing the edges between particular nodes. By solving the MST, we then obtain the risk causation phrase, the emergency measure phrase, and the dependencies relations.
Classification and mathematical modeling of infrastructure interdependencies
Published in Sustainable and Resilient Infrastructure, 2021
Neetesh Sharma, Fabrizio Nocera, Paolo Gardoni
Following Sharma and Gardoni (2019a), we represent infrastructure using graph theory. Graphs are mathematical structures amounting from pairwise related objects called vertices (points or nodes) and the relation between a pair of nodes as edges (arcs, lines or links.) Mathematically, a graph is written as , where is the set of nodes and is the set of links. Sharma and Gardoni (2019a) defined networks as graphs in which the nodes and links possess attributes like names, hierarchy, functions, type and state variables in addition to their topological identities (i.e. the pairwise relations that define the graphs.)Thus, an infrastructure is represented as a collection of networks, where each network captures a specific feature/function of the infrastructure (e.g. a network can describe the connectivity and physical damage of the infrastructure, and a flow network can describe its functionality.) The collection of all networks is written as , where superscript represents the quantities for network .