CliqueA clique (AusE, CanE, ˈkliːk or ˈklɪk), in the social sciences, is a group of individuals who interact with one another and share similar interests rather than with others. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popularity. Although cliques are most commonly studied during adolescence and middle childhood development, they exist in all age groups. They are often bound together by shared social characteristics such as ethnicity and socioeconomic status.
K shortest path routingThe k shortest path routing problem is a generalization of the shortest path routing problem in a given network. It asks not only about a shortest path but also about next k−1 shortest paths (which may be longer than the shortest path). A variation of the problem is the loopless k shortest paths. Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm. Since 1957 many papers were published on the k shortest path routing problem. Most of the fundamental works were done between 1960s and 2001.
Graph powerIn graph theory, a branch of mathematics, the kth power G^k of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G^2 is called the square of G, G^3 is called the cube of G, etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.
Adjacency listIn graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs. An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighbouring vertices or edges.
TreewidthIn graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.
Six degrees of separationSix degrees of separation is the idea that all people are six or fewer social connections away from each other. As a result, a chain of "friend of a friend" statements can be made to connect any two people in a maximum of six steps. It is also known as the six handshakes rule. The concept was originally set out in a 1929 short story by Frigyes Karinthy, in which a group of people play a game of trying to connect any person in the world to themselves by a chain of five others.
Maximum flow problemIn optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem. The maximum flow problem was first formulated in 1954 by T.
Logical matrixA logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science.
Minimum spanning treeA minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.
Shortest path problemIn graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment.
