Science > Physics > Quantum Gravity 1427: Retyping: Nearest Neighbor Graphs and Matrices in Computers, Cryptography, Computational Complexity
| Topic: |
Science > Physics |
| User: |
"OsherD" |
| Date: |
20 May 2007 10:12:50 AM |
| Object: |
Quantum Gravity 1427: Retyping: Nearest Neighbor Graphs and Matrices in Computers, Cryptography, Computational Complexity |
From Osher Doctorow
This post didn't appear right after I typed it, so I'm retyping it:
From Osher Doctorow
The "Nearest Neighbor" idea has many applications to:
1) Computer theory and practice
2) Cryptography
3) Computational Complexity
See:
4) Wolfram: "Adjacency matrix"
5) Wolfram: "Incidence matrix"
6) Wikipedia "Adjacency matrix"
7) Wikipedia "Spectral graph theory"
8) Wikipedia "Spectral gap"
9) Wikipedia "Expander graph"
10) Wikipedia "Regular graph"
It turns out that a graph is regular iff the all 1 vector is an
eigenvector of its adjacency matrix and a graph is both connected and
regular iff the all 1 matrix is a linear combination of powers of the
adjacency matrix.
Osher Doctorow
.
|
|
| User: "kunzmilan" |
|
| Title: Re: Quantum Gravity 1427: Retyping: Nearest Neighbor Graphs and Matrices in Computers, Cryptography, Computational Complexity |
21 May 2007 02:52:48 AM |
|
|
On May 20, 5:12 pm, OsherD <mdocto...@ca.rr.com> wrote:
From Osher Doctorow
This post didn't appear right after I typed it, so I'm retyping it:
From Osher Doctorow
The "Nearest Neighbor" idea has many applications to:
1) Computer theory and practice
2) Cryptography
3) Computational Complexity
See:
4) Wolfram: "Adjacency matrix"
5) Wolfram: "Incidence matrix"
6) Wikipedia "Adjacency matrix"
7) Wikipedia "Spectral graph theory"
8) Wikipedia "Spectral gap"
9) Wikipedia "Expander graph"
10) Wikipedia "Regular graph"
It turns out that a graph is regular iff the all 1 vector is an
eigenvector of its adjacency matrix and a graph is both connected and
regular iff the all 1 matrix is a linear combination of powers of the
adjacency matrix.
Osher Doctorow
Adjacency matrices, and distance matrices are connected with physical
properties of chemical compounds, as boiling points or spectras are.
There exist a branch of computational chemistry studying them.
kunzmilan
.
|
|
|
|
|
Related Articles |
|
|
