Hola Erica. Bienvenida al foro.
Con respecto a tus preguntas del árbol B
es posible la existencia de claves duplicadas solo si no están en el mismo nodo??
No no es posible. El árbol b es un método de "indexación" de registros, y esta indexación se lleva acabo a partir de su llave primaria o secundaria, las cuales deben ser únicas ne todo el árbol.
La inserción de elementos en un árbol B se realiza de forma aleatoria?
Definitivamente NO. Si bien la estructura interna de un árbol B puede parecer desordenada, las claves mantienen un orden SIEMPRE, por lo que la inserción de un elemento nuevo en el árbol se hace en el lugar específico y no aleatoriamente.
Si tenés alguna duda más, el artículo en Wikipedia sobre este tema es bastante claro.
http://es.wikipedia.org/wiki/B-tree
Con respecto al tema de los grafos, el concepto de recorrido en profundidad es bastante simple,
en este documento sale bien explicado el procedimiento.