Graph Theory

0.0(0)
studied byStudied by 0 people
0.0(0)
full-widthCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/16

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

17 Terms

1
New cards

Graph Theory

a branch of discrete math that deals with the study of objects and their relations

2
New cards

Graph

consists of vertices and edges

<p>consists of vertices and edges</p>
3
New cards

Vertices

are points in the graph

<p>are points in the graph</p>
4
New cards

Edges

are lines “connecting” two distinct vertices

<p>are lines “connecting” two distinct vertices</p>
5
New cards

Adjacent

two distinct vertices are said to be adjacent if and only if they are “connected” by a line. Also, two distinct edges are said to be adjacent if and only if the share a common vertex

<p>two distinct vertices are said to be adjacent if and only if they are “connected” by a line. Also, two distinct edges are said to be adjacent if and only if the share a common vertex</p>
6
New cards

Walk

a u-v walk is a sequence of vertices beginning with u and ending at v such that consecutive vertices in the sequence are adjacent

<p>a u-v walk is a sequence of vertices beginning with u and ending at v such that consecutive vertices in the sequence are adjacent</p>
7
New cards

Closed walk

a walk where the beginning and ending vertex are the same

<p>a walk where the<strong> beginning and ending vertex are the same</strong></p>
8
New cards

Trail

a u-v trail is a u-v walk in which no edge is traversed more than once

<p>a u-v trail is a u-v walk in which <strong>no edge is traversed more than once</strong></p>
9
New cards

Path

a u-v path is indeed a u-v walk in which no vertices are repeated

<p>a u-v path is indeed a u-v walk in <strong>which no vertices are repeated</strong></p>
10
New cards

Circuit

a closed trail of length 3 or more
(like closed trail)

<p>a closed trail of length 3 or more<br>(like closed trail)</p>
11
New cards

Cycle

a circuit that repeats no vertex, except for the first and last
(like closed path)

<p>a circuit that repeats no vertex, except for the first and last<br>(like closed path)</p>
12
New cards

Distance

the distance between u and v is the smallest length of any u-v path

<p>the distance between u and v is the smallest length of any u-v path</p>
13
New cards

Diameter

the greatest distance between any two vertices of a connected graph

<p>the greatest distance between any two vertices of a connected graph</p>
14
New cards

Complete graph

every two distinct vertices of the graph is adjacent with each other

15
New cards

Degree

the number of edges “connected” with v is called the degree of v

<p>the number of edges “connected” with v is called the degree of v</p>
16
New cards

Order

the number of vertices on a graph

<p>the number of vertices on a graph</p>
17
New cards

Size

the number of edges on a graph

<p>the number of edges on a graph</p>