Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
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
Normal Size Small Size show me how
Discrete test 2
| Question | Answer |
|---|---|
| who was Sir Isaac Newton? | he was an English mathematician, In addition to his work on calculus, as a mathematician, he contributed to the study of power series, and generalised the binomial theorem to non-integer exponents |
| Who is Frank Ruskey? | Frank Ruskey is the author of the original Combinatorial Object Server, Notably, Frank was the PhD supervisor of Joe Sawada and Aaron Williams. His favourite decoding problem produced the message Beer and Basketball |
| Who was Julius Peter Christian Petersen? | 1839-1910) was a Danish mathematician, His contributions to the field of mathematics led to the birth of graph theory and he made what is now known as Peterson graph |
| Who is Brendan Mckay? | born 1951) is an Australian computer scientist, One of McKay’s main contributions has been a practical algorithm for the graph isomorphism problem and its software implementation NAUTY (No AUTomorphisms, Yes?) |
| The length of a walk is.. | the number of edges in the walk |
| A trail is.. | a walk with no repeated edges |
| A path is.. | an open walk that has no repeated edges |
| A circuit is.. | a closed walk with no repeated edges |
| A cycle is | a circuit with length at least 1 with no repeated vertices, except the first and last |
| what is isomorphism | two graphs are isomorphic if they are a bijection, both one to one and onto, they must have same number of edges, vertices and degree sequence, have the same cycles and it must be true for all n |
| if two graphs have the same degree sequence are they isomorphic? | not necessarily but they could be. |
| What was found from Quanta Magazine | Main Result (after an update in 2017): Graph Isomorphism can be solved in quasi-polynomial time |
| What is the handshaking theorumn? | sum of the degrees = 2(# edges), each edge gets counted twice |
| What does the n-cube correspond to? | the vertices correspond to length n bit strings, if they differ by a bit they are connected, to obtain it take two copies of the n-1 cube and join the corresponding vertices |
| What makes a simple graph bipartite | if the vertices can be partitioned into two disjoint sets, making all the vertices isolated if they were separated. or if and only if it is possible to color the vertices with two colors such that no two adjacent vertices have the same color |
| what is a multigraph | when multiple edges are allowed between two vertices |
| what is a pseudograph | if a multigraph also allows edges back to itself |
| what is the order of the graph | number of vertices, n |
| what is the size of a graph | number of edges,m |
| can you make a graph with 5 vertices that have degrees 0, 1, 2, 3, 4 | not possible 2 vertices will always have the same degree |
Created by:
jayne_