Graphs And Networks Flashcards
What is a subgraph?
A subgraph is part of a graph.
What is a graph?
A graph consists on nodes which are connected by arcs.
When is a graph weighted?
When it has a number associated with each edge.
What is the degree or valency or order of a vertex?
The number of edges incident to it.
What is a path?
A path is a finite sequence of edges,such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
What is a walk?
A walk is a path in which you are permitted to return to verticies more than once.
What is a cycle?
A closed path.
When are verticies connected?
If there is a path between them. A graph is connected if all it’s verticies are connected.
What is a loop?
A loop is an edge that starts and finishes as the same vertex.
What is a simple graph?
A graph which there are no loops and not more than one edge connecting any pair of verticies.
What are digraphs?
Is the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph.
What is a tree?
A connected graph with no cycles.
What is a spanning tree?
A spanning tree of a graph which includes all the verticies of the graph and is also a tree.
What is a bipartite graph?
It consists of two sets of verticies. Arcs only connect nodes between nodes in opposite sets.
What is a complete graph?
Is a graph in which every vertex is directly connected by an edge to each of the other verticies. If the graph has n verticies it is denoted by Kn.
