Save
Upgrade to remove ads
Busy. Please wait.
Log in with Clever
or
show password
Forgot Password?
Don't have an account?  Sign up 
Sign up using Clever
or
Username is available taken
show password


Make sure to remember your password. If you forget it there is no way for StudyStack to send you a reset link. You would need to create a new account. Your email address is only used to allow you to reset your password. See our Privacy Policy and Terms of Service.

Already a StudyStack user? Log In

Reset Password
Enter the associated with your account, and we'll email you a link to reset your password.
focusNode
Didn't know it?
click below
 
Knew it?
click below
Don't Know
Remaining cards (0)
Know
0:00
edit
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

  Normal Size     Small Size show me how

Apps terms.

QuestionAnswer
Graph A diagram that consists of a set of points called vertices or nodes that are joined by a set of lines called edges or arcs.
Adjacent vertices Two vertices are said to be adjacent if they are at opposite ends of an edge. That is, adjacent variables share a common edge.
Multiple edges Two or more edges which connect the same vertices are called multiple edges.
Loop A loop is an edge in a graph that joins a vertex to itself. In other words, a loop starts and ends at the same vertex. If the vertex has a loop then the vertex is said to be adjacent to itself.
Isolated vertex A vertex that is not connected to any other vertex in a graph by an edge is called an isolated vertex. In such cases the graph is said to be disconnected or unconnected.
Degree of a vertex The degree or order of a graph vertex is the number of graph edges which touch that vertex. If the vertex has a loop then the loop edge touches the vertex twice.
Sum of degrees For any undirected graph, the sum of the degrees of the vertices equals twice the number of edges.
In-degree and out-degree For a directed graph, some of the edges come into a vertex and other edges leave the vertex. Thus, the order or degree of a vertex makes no sense.
Vertex and edge sets. This method of representing a graph requires one to list the set of vertices and the set of all edges of the given graph.
Adjacency list. An adjacency list is simply a list of the vertices of the graph that are adjacent.
Adjacency matrix. An adjacency matrix for a graph containing n vertices is a square matrix of order n x n in which the entry in row i and column j is the number of edges joining vertices i and j. In an adjacency matrix a loop is counted as one edge.
Why is a loop counted as an edge in an adjacency matrix? There is only one edge that starts at the vertex and then returns to the same vertex.
Weighted graph. A graph in which each edge is labelled with a number used to represent some quantity associated with the edge. The number on an edge is called a weight. The weight of the edge is often referred to as the cost.
Subgraph. A graph that contains no vertices or edges that are not in the original graph. In other words, it is a graph that is part of another graph with no new vertices or edges.
Bipartite graphs. A graph whose vertices can be split into two distinct groups in such a way that each edge of the graph joins a vertex in the first group to a vertex in the second group.
Complete bipartite graph. A graph that has every vertex in the first group connected to every vertex in the second group.
How many edges are in a complete bipartite graph? The number of edges in a complete bipartite graph is given by m x n where m is the number of vertices in the first group and n is the number of vertices in the second group.
Testing if a graph is bipartite. Colour a vertex. Colour all the vertices adjacent to it a different colour. Continue this process until all vertices are either of the colours. If every edge of the graph has a different colour at its ends then the graph is bipartite.
Adjacent vertices. Two vertices are said to be adjacent if they are connected by an edge.
Adjacency matrix (directed). An adjacency matrix for a directed graph containing n vertices is a square matrix of order n x n in which the entry in row i and column j is the number of directed edges joining the vertex i and j in the direction i to j.
Matrix properties of a directed graph. The entry in row i, column j is the number of directed edges there are joining vertex i to vertex j The entries in the matrix are not symmetrical across the leading diagonal. If the graph has no loops then the leading diagonal of the matrix shows only 0.
Planar graph. An undirected graph that can be drawn on a plane without any of its edges crossing.
Planar graphs and the number of vertices, edges, and faces. Any section closed off by edges and vertices in a planar graph are referred to as faces.
Euler's formula. For any connected planar graph if v is the number of vertices, f is the number of faces and e the number of edges then: v + f - e= 2.
What is Euler's formula used for? Euler's formula may be used to verify that a simple connected graph is planar and to find either the number of vertices or the number of faces or the number of edges given the other two.
Platonic solids. A 3 dimensional shape where each face is the same rectangular polygon and the same number of faces meet at each vertex.
Five platonic solids. Tetrahedron, cube, octahedron, dodecahedron, and icosahedron.
Tetrahedron qualities. 4 triangular faces, 4 vertices (3 triangles meet at each vertex), 6 edges (3 edges meet at each vertex).
Cube qualities. 6 square faces, 8 vertices (3 squares meet at each vertex), 12 edges (3 edges meet at each vertex).
Octahedron qualities. 8 triangular faces, 6 vertices (4 triangles meet at each vertex), 12 edges (4 edges meet at each vertex).
Dodecahedron qualities. 12 pentagonal faces, 20 vertices (3 pentagons meet at each vertex), 30 edges (3 edges meet at each vertex).
Icosahedron qualities. 20 triangular faces, 12 vertices (5 triangles meet at each vertex), 30 edges (5 edges meet at each vertex).
Network. A graph which represents real-life applications.
Walk. In a graph is an alternating sequence of vertices and connecting edges A walk is any route through a graph from vertex to vertex along the connecting edges. A walk can start or end on the same or different vertices. Can include repeated vertices/ edges.
Open walk. A walk that starts and finishes at different vertices.
Closed walk. A walk that starts and finishes at the same vertex.
Length of a walk. The number of edges of the walk.
Trail. A walk in which no edge is repeated.
Open trail. A walk in which no edge is repeated and the trail starts at one vertex and ends at a different vertex.
Closed trail. A walk in which no edge is repeated and the trail starts at one vertex and ends at the same vertex.
Path. In a graph is a walk in which all the edges and all the vertices are different. There is no repeat use of edges and no repeat use of vertices other than starting and ending at the same vertex.
Open path. Is a walk in which no edge is repeated and no vertex is repeated. Open paths start and end at different vertices.
Closed path. A walk in which no edge is repeated and no vertex is repeated. Start and end at the same vertex.
Length of a path. The length of the path is the number of edges in the path.
Cycle. A closed path. A walk which begins and ends at the same vertex and which has no repeated edges or vertices except the first.
Circuit. A closed trail. A walk which begins and ends at the same vertex, edges may not be repeated whereas vertices may be repeated.
Bridge. An edge in a connected graph that, if removed, leaves the graph disconnected.
Walk summary. Vertices may repeat, edges may repeat.
Trail summary. Vertices may repeat, edges cannot repeat.
Path summary. Vertices cannot repeat, edges cannot repeat.
Cycle summary. Vertices cannot repeat, edges cannot repeat, must start and end at the same vertex.
Circuit summary. Vertices may repeat, edges cannot repeat, must start and end at the same vertex.
Eulerian trail. A trail in a connected graph that travels every edge in the graph only once.
Eulerian circuit. If an Eulerian trail is closed, it is said to be an Eulerian circuit.
Eulerian graph. A connected graph is said to be an Eulerian graph if it has a closed trail and includes every edge once only. They only have even vertices.
Determining if a graph is Eulerian. Every vertex must be of even degree, you must start and finish at the same vertex, and every edge must be traversed only once.
Semi-Eulerian trail. If an Eulerian trail is open, that is, it begins and ends at different vertices, it is said to be a semi-Eulerian trail.
Semi-Eulerian graphs. A connected graph is said to be a semi-Eulerian graph if it has a semi-Eulerian trail. It is semi-Eulerian if you can start at a vertex, traverse through every edge only once, and end up at a different vertex. Must have exactly two odd vertices.
Determining if a graph is semi-Eulerian. Only two vertices can be of odd degree, every other vertex must be of even degree. You must start the semi-Eulerian trail at a vertex with odd degree and end at the other vertex with odd degree. Every edge must be traversed only once.
Hamiltonian path. A path in a connected graph that includes every vertex in the graph once only and it starts and finishes at different vertices.
Hamiltonian cycle. If a Hamiltonian path is closed, then the graph is said to be Hamiltonian and the closed path (or cycle) is said to be a Hamiltonian cycle. A Hamiltonian cycle is a cycle that includes every vertex once, and begins and ends at the same vertex.
Semi-Hamiltonian graph. A connected graph that contains a Hamiltonian path but not a Hamiltonian cycle.
Properties of Hamiltonian graphs (part 1). Connected graphs. Hamiltonian cycle can be converted into a Hamiltonian path by removing one of its edges. A Hamiltonian path can be converted to a Hamiltonian cycle if the endpoints of the Hamiltonian path are adjacent.
Properties of Hamiltonian graphs (part 2). All complete graphs, that is Kn are Hamiltonian. Complete bipartite graphs which have the same number of vertices in each group are Hamiltonian.
Created by: Samara Hayes
 

 



Voices

Use these flashcards to help memorize information. Look at the large card and try to recall what is on the other side. Then click the card to flip it. If you knew the answer, click the green Know box. Otherwise, click the red Don't know box.

When you've placed seven or more cards in the Don't know box, click "retry" to try those cards again.

If you've accidentally put the card in the wrong box, just click on the card to take it out of the box.

You can also use your keyboard to move the cards as follows:

If you are logged in to your account, this website will remember which cards you know and don't know so that they are in the same box the next time you log in.

When you need a break, try one of the other activities listed below the flashcards like Matching, Snowman, or Hungry Bug. Although it may feel like you're playing a game, your brain is still making more connections with the information to help you out.

To see how well you know the information, try the Quiz or Test activity.

Pass complete!
"Know" box contains:
Time elapsed:
Retries:
restart all cards