Graph Theory Flashcards
Points are normally called…
Vertices or Nodes
Lines are called…
Edges or Arcs
The graph is called a NETWORK (or weighted graph) if…
the graph has a number linked to each edge
two vertices are connected if…
there is an edge joining them
a graph is connected if…
all pairs of vertices are connected
a simple graph is…
one in which there is no loops and at most one edge connects any pair of vertices
the DEGREE or ORDER of a vertex is…
the number of edges connected to the vertex
a graph that has directed edges is called a…
directed graph or diagraph
a complete graph (Kn) is..
a graph in which every vertex is connected by an edge to each of the other vertices
what is a Bipartite Graph?
has two sets of vertices and the edges only connect vertices from one set to the other
a trail is…
a sequence of edges of a graph such that the second vertex of each edge is the first vertex of the next edge
a path is…
a trail such that no vertex is visited more than once
a cycle is…
a closed path with at least one edge
a Hamiltonian Cycle is…
a cycle that visits every vertex of a graph
a Eulerian trail is …
a trail that uses all of the edges of a graph
