SoS Quiz - Graph Theory Terms

mathematical graph

set of ordered pairs (V, E) that represent the vertices and edges of the graph

adjacent

when two vertices are connected by an edge

multigraph

multiple edges are permitted between two vertices. Loops may also be allowed

undirected graph

no directions of paths

directed graph

all paths have directions

mixed graph

some paths have directions

unweighted graph

edges have no weights/scores

weighted graph

weightings are assigned to edges. The meaning of the weight is dependent on application.

bipartite graph

graphs that have some path where they only connect from set U to set V. must contain even cycles

degree

number of edges that are adjacent to a vertex. max degree: largest degree between all vertices. min degree: smallest degree between all the vertices (can be 0)

indegree

how many edges point baco into the vertex

outdegree how many edges point out of the vertex

how many edges point out of the vertex

multiplicity

how many edges share the same vertex (multiplicity of a graph is max multiplicity of edges)

degree sequence

lists degrees of graph, unordered

subgraph

subset of a larger graph

cut-edge

an edge whose deletion increases the amount of components (typically by isolating a vertex)

cut vertex

a vertex whose deletion increases the number of components.

walk

alternating sequence of vertices and edges (ending with a vertex).

closed walk

ends on same beginning vertex

open walk

ends on different vertex than starting

length of walk

the number of edges in a walk

trail

A walk where no edge is repeated

circuit

a closed trail

Eulerian Circuit

A circuit that contains every edge of a graph once

Hamiltonian Circuit

a tour that starts at a vertex of a graph and visits each vertex once and only once, returning to where it started

algebraic graph analysis

studying graphs through linear algebra

spectral graph analysis

studying graphs utilizing matrices and eigenvalues

combinatoric graph analysis

using cycles, cut edges, and other metrics to analyze a graph

algorithmic graph analysis

step by step solution (A*, travelling salseman)

Geometric graph analysis

utilizing geometric shapes such as flat graphs, location information, etc to analyze graph

adjacency matrix

indicates what vertices are adjacent to each other based on their edges

incidence

shows whether an edge connects to some end point

degree centrality

shows the degree of the vertex

Geodesic path

The shortest path between two vertices

Closeness Centrality

mean geodesic distance from some vertex

small world effect

the mean geodesic distance between vertex pairs is small compared to the size of a network

algebraic connectivity

degree cf connectivity of the graph (second smallest eigenvalue)

connectivity

measure of robustness of a network

cyclicity

the largest eigenvalue and its eigenvectors give an idea of how many cycles are in a graph

complexity of graph

cyclomatic complexity = (num_edges) - (num_nodes) +2*(num_connected_components)

transivity and the global clustering coefficient

C=(3*n_triangles)/n_connected_triples

Max-Flow Min-Cut Theorem

The value of the max flow equals the capacity of the minimum cut.

connectivity

how well connected something is

vulnerability

how much a system is compromised under certain conditions

robustness

how resilient a system is

betwenness

what are the bottlenecks

clustering

how easy it is to divide a graph into semi-independent segments

max-flow

logistics or distribution networks

capability

using cycles to determine a networks capability

focused model

can determine what nodes are critical to capability