Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
23 Cards in this Set
- Front
- Back
|
Graph |
A diagram representing a system of connections among two or more things by a number of distinctive dots, lines, bars, etc |
|
|
Vertex |
(Node) one of the two basic units out of which graphs are constructed. Vertices of graphs are often considered to be atomic objects, with no internal structure. |
|
|
Edge |
An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two (or in hypergraphs, more) vertices to which it is attached, called its endpoints. Edges may be directed or undirected; undirected edges are also called lines and directed edges are also called arcs or arrows. In an undirected simple graph, an edge may be represented as the set of its vertices, and in a directed simple graph it may be represented as an ordered pair of its vertices. An edge that connects vertices x and y is sometimes written xy. |
|
|
Path |
A path may either be a walk (a sequence of vertices and edges, with both endpoints of an edge appearing adjacent to it in the sequence) or a simple path (a walk with no repetitions of vertices or edges), depending on the source. Important special cases include induced paths and shortest paths. |
|
|
Cycle |
A cycle may either refer to a closed walk (also called a tour) or more specifically to a closed walk without repeated vertices or edges (a simple cycle). In either case, the choice of starting vertex is usually considered unimportant: cyclic permutations of the walk produce the same cycle. Important special cases of cycles include Hamiltonian cycles, induced cycles, peripheral cycles, and the shortest cycle, which defines the girth of a graph. A k-cycle is a cycle of length k; for instance a 2-cycle is a digon and a 3-cycle is a triangle. A cycle graph is a graph that is itself a simple cycle; a cycle graph with n vertices is commonly denoted Cn. The cycle space is a vector space generated by simple cycles in a graph. |
|
|
Hamilton Cycle |
A Hamiltonian path or Hamiltonian cycle is a simple spanning path or simple spanning cycle: it covers all of the vertices in the graph exactly once. A graph is Hamiltonian if it contains a Hamiiltonian cycle, and traceable if it contains a Hamiltonian path. |
|
|
Eulerian Cycle |
a walk that uses every edge of a graph exactly once. An Eulerian circuit (also called an Eulerian cycle or an Euler tour) is a closed walk that uses every edge exactly once. An Eulerian graph is a graph that has an Eulerian circuit. For an undirected graph, this means that the graph is connected and every vertex has even degree. For a directed graph, this means that the graph is strongly connected and every vertex has in-degree equal to the out-degree. In some cases, the connectivity requirement is loosened, and a graph meeting only the degree requirements is called Eulerian. |
|
|
Vertex set |
The set of vertices of a given graph G, sometimes denoted by V(G) |
|
|
Edge set |
The set of vertices of a given graph G, sometimes denoted by V(G) |
|
|
Subgraph |
A subgraph of a graph G is another graph formed from a subset of the vertices and edges of G. The vertex subset must include all endpoints of the edge subset, but may also include additional vertices. A spanning subgraph is one that includes all vertices of the graph; an induced subgraph is one that includes all the edges whose endpoints belong to the vertex subset. |
|
|
Connected graph |
one in which each pair of vertices forms the endpoints of a path. Higher forms of connectivity include strong connectivity in directed graphs (for each two vertices there are paths from one to the other in both directions), k-vertex-connected graphs (removing fewer than k vertices cannot disconnect the graph), and k-edge-connected graphs (removing fewer than k edges cannot disconnect the graph). |
|
|
Loop |
an edge both of whose endpoints are the same vertex. It forms a cycle of length 1. These are not allowed in simple graphs. |
|
|
Simple Graph |
a graph with no loops and with no multiple adjacencies. That is, each edge connects two distinct endpoints and no two edges have the same endpoints. A simple edge is an edge that is not part of a multiple adjacency. In many cases, graphs are assumed to be simple unless specified otherwise. |
|
|
Degree of a graph |
number of incident edges.[2] The degree of a graph G (or its maximum degree) is the maximum of the degrees of its vertices, often denoted Δ(G); the minimum degree of G is the minimum of its vertex degrees, often denoted δ(G). Degree is sometimes called valency; the degree of v in G may be denoted dG(v), d(G), or deg(v). The total degree is the sum of the degrees of all vertices; by the handshaking lemma it is an even number. The degree sequence is the collection of degrees of all vertices, in sorted order from largest to smallest. In a directed graph, one may distinguish the in-degree (number of incoming edges) and out-degree (number of outgoing edges).[2] |
|
|
Digraph |
one in which the edges have a distinguished direction, from one vertex to another.[2] In a mixed graph, a directed edge is again one that has a distinguished direction; directed edges may also be called arcs or arrows. |
|
|
Tree |
an undirected graph that is both connected and acyclic, or a directed graph in which there exists a unique walk from one vertex (the root of the tree) to all remaining vertices. |
|
|
Spanning Tree |
subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (but see Spanning forests below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself). |
|
|
Complete Graph |
one in which every two vertices are adjacent: all edges that could exist are present. A complete graph with n vertices is often denoted Kn. A complete bipartite graph is one in which every two vertices on opposite sides of the partition of vertices are adjacent. A complete bipartite graph with a vertices on one side of the partition and b vertices on the other side is often denoted Ka,b. The same terminology and notation has also been extended to complete multipartite graphs, graphs in which the vertices are divided into more than two subsets and every pair of vertices in different subsets are adjacent; if the numbers of vertices in the subsets are a, b, c, ... then this graph is denoted Ka, b, c, .... |
|
|
Bipartite Graph |
a graph with no odd cycles; equivalently, it is a graph that may be properly colored with two colors. Bipartite graphs are often written G = (U,V,E) where U and V are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring. |
|
|
Planar Graph |
a graph that has an embedding onto the Euclidean plane. A plane graph is a planar graph for which a particular embedding has already been fixed. A k-planar graph is one that can be drawn in the plane with at most k crossings per edge. |
|
|
Network |
A graph in which attributes (e.g. names) are associated with the nodes and/or edges. |
|
|
Weight Of An Edge |
A weight is a numerical value, assigned as a label to a vertex or edge of a graph. A weighted graph is a graph whose vertices or edges have been assigned weights; more specifically, a vertex-weighted graph has weights on its vertices and an edge-weighted graph has weights on its edges. The weight of a subgraph is the sum of the weights of the vertices or edges within that subgraph. |
|
|
Triangle inequality |
triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side |
